Codeforces 986E — Prince's Problem

1package main2 3import (4	"bufio"5	. "fmt"6	"io"7	"math/bits"8)9 10// https://github.com/EndlessCheng11func cf986E(in io.Reader, _w io.Writer) {12	out := bufio.NewWriter(_w)13	defer out.Flush()14	abs := func(x int) int {15		if x < 0 {16			return -x17		}18		return x19	}20	gcd := func(a, b int) int {21		for a != 0 {22			a, b = b%a, a23		}24		return b25	}26 27	const MX int = 1e7 + 128	lpf := [MX]int{}29	for i := 2; i < MX; i++ {30		if lpf[i] == 0 {31			for j := i; j < MX; j += i {32				if lpf[j] == 0 {33					lpf[j] = i34				}35			}36		}37	}38 39	const mod = 1_000_000_00740	pow := func(x, n int) int {41		res := 142		for ; n > 0; n /= 2 {43			if n%2 > 0 {44				res = res * x % mod45			}46			x = x * x % mod47		}48		return res49	}50 51	var n, q int52	Fscan(in, &n)53	g := make([][]int, n)54	for range n - 1 {55		var v, w int56		Fscan(in, &v, &w)57		v--58		w--59		g[v] = append(g[v], w)60		g[w] = append(g[w], v)61	}62	pa := make([][17]int, n)63	dep := make([]int, n)64	var build func(int, int)65	build = func(v, p int) {66		pa[v][0] = p67		for _, w := range g[v] {68			if w != p {69				dep[w] = dep[v] + 170				build(w, v)71			}72		}73	}74	build(0, -1)75	mx := bits.Len(uint(n))76	for i := range mx - 1 {77		for x := range pa {78			p := pa[x][i]79			if p != -1 {80				pa[x][i+1] = pa[p][i]81			} else {82				pa[x][i+1] = -183			}84		}85	}86	uptoDep := func(v, d int) int {87		for k := uint32(dep[v] - d); k > 0; k &= k - 1 {88			v = pa[v][bits.TrailingZeros32(k)]89		}90		return v91	}92	getLCA := func(v, w int) int {93		if dep[v] > dep[w] {94			v, w = w, v95		}96		w = uptoDep(w, dep[v])97		if w == v {98			return v99		}100		for i := mx - 1; i >= 0; i-- {101			pv, pw := pa[v][i], pa[w][i]102			if pv != pw {103				v, w = pv, pw104			}105		}106		return pa[v][0]107	}108 109	a := make([]int, n)110	for i := range a {111		Fscan(in, &a[i])112	}113 114	type pair struct{ x, i int }115	qs := make([][]pair, n)116	Fscan(in, &q)117	ans := make([]int, q)118	for i := range ans {119		ans[i] = 1120		var v, w, x int121		Fscan(in, &v, &w, &x)122		v--123		w--124		lca := getLCA(v, w)125		qs[v] = append(qs[v], pair{x, i})126		qs[w] = append(qs[w], pair{x, i})127		qs[lca] = append(qs[lca], pair{-x, i})128	}129 130	mulCnt := map[int]map[int]int{}131	var dfs func(int, int)132	dfs = func(v, fa int) {133		for x := a[v]; x > 1; {134			p := lpf[x]135			mul := p136			for x /= p; x%p == 0; x /= p {137				mul *= p138			}139			if mulCnt[p] == nil {140				mulCnt[p] = map[int]int{}141			}142			mulCnt[p][mul]++143		}144 145		for _, q := range qs[v] {146			res := 1147			for x := abs(q.x); x > 1; {148				p := lpf[x]149				mul := p150				for x /= p; x%p == 0; x /= p {151					mul *= p152				}153				for m, c := range mulCnt[p] {154					res = res * pow(min(m, mul), c) % mod155				}156			}157			if q.x > 0 {158				ans[q.i] = ans[q.i] * res % mod159			} else {160				ans[q.i] = ans[q.i] * pow(res, mod-3) % mod * gcd(-q.x, a[v]) % mod161			}162		}163 164		for _, w := range g[v] {165			if w != fa {166				dfs(w, v)167			}168		}169 170		for x := a[v]; x > 1; {171			p := lpf[x]172			mul := p173			for x /= p; x%p == 0; x /= p {174				mul *= p175			}176			mulCnt[p][mul]--177		}178	}179	dfs(0, -1)180 181	for _, v := range ans {182		Fprintln(out, v)183	}184}185 186//func main() { cf986E(bufio.NewReader(os.Stdin), os.Stdout) }187