Codeforces986E Prince's Problem

未分类

先将每个询问差分为询问从根到点的路径 $gcd$ 之积，然后 dfs 树一遍离线处理。对于 $gcd(x,y)$ 可以看成是对于 $x,y$ 的每个质因子的指数取 min，因为 $10^7$ 内质数个数不多且指数小，可以开个桶来统计。具体来说，加入一个 $a^p$ 时将 $a$ 的桶里编号从 $1$ 到 $p$ 的部分加一，统计 $x$ 的时候将 $x$ 的每种质因子及其个数算出来（表示为 $a^p$），统计 $a$ 的桶里 $1$ 到 $p$ 的总和即为答案里这种质因子的指数。为了快速地实现质因数分解先用线性筛求出每个数最小的质因子，即可 $\mathcal O(\log n)$ 完成单次分解。

#include <iostream>
#include <cstdio>
#include <vector>
const int MAXN = 1e5;
const int MAXV = 1e7;
const int MOD = 1e9 + 7;
struct Query {
  int id, x, v;
  Query() : id(0), x(0), v(0) {}
  Query(int _id, int _x, int _v) : id(_id), x(_x), v(_v) {}
};
int n, m, prime_tot, edge, idx;
int prime[MAXV | 1], min_prime[MAXV | 1], prime_id[MAXV | 1], fst[MAXN | 1], a[MAXN | 1], ans[MAXN | 1];
int dfn[MAXN | 1], topf[MAXN | 1], father[MAXN | 1], size[MAXN | 1], son[MAXN | 1], depth[MAXN | 1];
short book[25][664580];
bool vis[MAXV | 1];
std::vector < Query > queries[MAXN | 1];
struct Edge {
  int to, nxt;
  Edge() : to(0), nxt(0) {}
  Edge(int a, int b) : to(b), nxt(fst[a]) {}
} e[MAXN << 1 | 1];
inline int read( ){
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
inline void addEdge(int a, int b) {
  e[++edge] = Edge(a, b);
  fst[a] = edge;
}
void dfs1(int x, int y) {
  father[x] = y;
  depth[x] = depth[y] + 1;
  dfn[x] = ++idx;
  size[x] = 1;
  for (int k = fst[x]; k; k = e[k].nxt) {
    int to = e[k].to;
    if (to == y) continue;
    dfs1(to, x);
    size[x] += size[to];
    if (size[to] > size[son[x]]) son[x] = to;
  }
}
void dfs2(int x, int ftop) {
  topf[x] = ftop;
  if (!son[x]) return;
  dfs2(son[x], ftop);
  for (int k = fst[x]; k; k = e[k].nxt) {
    int to = e[k].to;
    if (to == father[x] || to == son[x]) continue;
    dfs2(to, to);
  }
}
int LCA(int x, int y) {
  while (topf[x] != topf[y]) {
    if (depth[topf[x]] < depth[topf[y]]) std::swap(x, y);
    x = father[topf[x]];
  }
  return depth[x] < depth[y] ? x : y;
}
int fast_pow(int x, int y, int mod) {
  int res = 1, base = x;
  while (y > 0) {
    if (y & 1) res = 1LL * res * base % mod;
    base = 1LL * base * base % mod;
    y >>= 1;
  }
  return res;
}
void update(int x, int v) {
  while (x != 1) {
    int times = 0;
    int min = min_prime[x];
    // printf("x=%d min=%d\n", x, min_prime[x]);
    while (x != 1 && min_prime[x] == min) {
      ++times;
      x /= min_prime[x];
    }
    for (int i = 1; i <= times; ++i) book[i][prime_id[min]] += v;
  }
}
int query(int v) {
  int res = 1;
  while (v != 1) {
    int times = 0;
    int min = min_prime[v];
    while (v != 1 && min_prime[v] == min) {
      ++times;
      v /= min_prime[v];
    }
    int sum = 0;
    for (int i = 1; i <= times; ++i) sum += book[i][prime_id[min]];
    res = 1LL * res * fast_pow(min, sum, MOD) % MOD;
  }
  return res;
}
void calc_dfs(int x) {
  update(a[x], 1);
  for (int k = fst[x]; k; k = e[k].nxt) {
    int to = e[k].to;
    if (to == father[x]) continue;
    calc_dfs(to);
  }
  for (std::vector < Query > :: iterator it = queries[x].begin(); it != queries[x].end(); ++it) {
    Query now = *it;
    int res = query(now.x);
    if (now.v == 1) ans[now.id] = 1LL * ans[now.id] * res % MOD;
    else ans[now.id] = 1LL * ans[now.id] * fast_pow(res, MOD - 2, MOD) % MOD;
  }
  update(a[x], -1);
}
int main() {
  n = read();
  for (int i = 1; i < n; ++i) {
    int u = read(), v = read();
    addEdge(u, v);
    addEdge(v, u);
  }
  for (int i = 1; i <= n; ++i) a[i] = read();
  for (int i = 2; i <= 1e7; ++i) {
    if (!vis[i]) {
      prime[++prime_tot] = i;
      min_prime[i] = i;
      prime_id[i] = prime_tot;
    }
    for (int j = 1; i * prime[j] <= 1e7 && j <= prime_tot; ++j) {
      vis[i * prime[j]] = 1;
      min_prime[i * prime[j]] = prime[j];
      if (i % prime[j] == 0) break;
    }
  }
  dfs1(1, 0);
  dfs2(1, 1);
  m = read();
  for (int i = 1; i <= m; ++i) {
    ans[i] = 1;
    int a = read(), b = read(), x = read();
    int lca = LCA(a, b);
    queries[a].push_back(Query(i, x, 1));
    queries[b].push_back(Query(i, x, 1));
    queries[lca].push_back(Query(i, x, -1));
    queries[father[lca]].push_back(Query(i, x, -1));
  }
  calc_dfs(1);
  for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
  return 0;
}