CodeForces，CodeForces - 986E Prince's Problem

Description

給一棵樹，每個點有點權 \(a_i\) ，每次給 \(u,v,x\) ，求 \(u\) 到 \(v\) 路徑上每個點的點權與 \(x\) 的 \(gcd\) 的積。

\(n,m\le 10^5,1\le a_i\le 10^7\)

Solution

離線，答案相當與四條從根出發的鏈拼起來，分解質因數。

#include<bits/stdc++.h>
using namespace std;template <class T> void read(T &x) {x = 0; bool flag = 0; char ch = getchar(); for (; ch < '0' || ch > '9'; ch = getchar()) flag |= ch == '-';for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - 48; flag ? x = ~x + 1 : 0;
}//#pragma GCC diagnostic error "-std=c++14"#define N 100010
#define rep(i, a, b) for (auto i = (a); i <= (b); ++i)
#define drp(i, a, b) for (auto i = (a); i >= (b); --i)
#define P 1000000007bool notPri[10000010];
int pri[664580 + 10], priCnt;void init(int n) {int m = sqrt(n + 0.5);rep(i, 2, m) if (!notPri[i]) for (int j = i * i; j <= n; j += i) notPri[j] = 1;rep(i, 2, n) if (!notPri[i]) pri[++priCnt] = i;
}vector<int> g[N];int fa[N][18], dep[N];
void dfs(int u) {rep(i, 1, 17) fa[u][i] = fa[fa[u][i - 1]][i - 1];for (int v : g[u]) if (v ^ fa[u][0]) fa[v][0] = u, dep[v] = dep[u] + 1, dfs(v);
}int getLca(int u, int v) {if (dep[u] < dep[v]) swap(u, v);drp(i, 17, 0) if (dep[fa[u][i]] >= dep[v]) u = fa[u][i]; if (u == v) return u;drp(i, 17, 0) if (fa[u][i] ^ fa[v][i]) u = fa[u][i], v = fa[v][i]; return fa[u][0];
}struct Data {int x, id;bool type;Data(int x = 0, int id = 0, bool type = 0) : x(x), id(id), type(type) {}
};vector<Data> q[N];int qpow(int x, int k) {int ret = 1;for (; k; k >>= 1, x = 1ll * x * x % P) if (k & 1) ret = 1ll * ret * x % P;return ret;
}int a[N], ans[N], cnt[664580 + 10][25];void update(int val, int del) {for (int i = 1; 1ll * pri[i] * pri[i] <= val; ++i) if (val % pri[i] == 0) {int p = 0;for (; val % pri[i] == 0; val /= pri[i], ++p);cnt[i][p] += del;}if (val != 1) cnt[lower_bound(pri + 1, pri + 1 + priCnt, val) - pri][1] += del;
}int query(int val) {int ret = 1;for (int i = 1; 1ll * pri[i] * pri[i] <= val; ++i) if (val % pri[i] == 0) {int p = 0, t = 0;for (; val % pri[i] == 0; val /= pri[i], ++p);rep(j, 1, p) t += cnt[i][j] * j;rep(j, p + 1, 24) t += cnt[i][j] * p;ret = 1ll * ret * qpow(pri[i], t) % P;}if (val == 1) return ret;int pos = lower_bound(pri + 1, pri + 1 + priCnt, val) - pri;int t = 0;rep(i, 1, 24) t += cnt[pos][i];return 1ll * ret * qpow(val, t) % P;
}void solve(int u) {update(a[u], 1);for (auto t : q[u]) {if (t.type) ans[t.id] = 1ll * ans[t.id] * query(t.x) % P;else ans[t.id] = 1ll * ans[t.id] * qpow(query(t.x), P - 2) % P;}for (int v : g[u]) if (v != fa[u][0]) solve(v);update(a[u], -1);
}#define pb push_backint main() {init(10000000);int n, m; read(n);rep(i, 2, n) {int u, v; read(u), read(v);g[u].pb(v), g[v].pb(u);}dep[1] = 1; dfs(1);rep(i, 1, n) read(a[i]);read(m);rep(i, 1, m) {int u, v, x; read(u), read(v), read(x);int lca = getLca(u, v);ans[i] = 1;q[u].pb(Data(x, i, 1)), q[v].pb(Data(x, i, 1)), q[lca].pb(Data(x, i, 0));if (lca != 1) q[fa[lca][0]].pb(Data(x, i, 0));}solve(1);rep(i, 1, m) printf("%d\n", ans[i]);return 0;
}