\(\gcd\) 一个性质：对于正整数 \(x\)， 重复 \(x\leftarrow \gcd(x, i)\)（\(i\ge 0\)）直到 \(x = 1\)，\(x\) 出现的值个数上限为 \(\log_2(x)+1\)
证明：考虑到 \(x\) 是逐渐变小，则在 \(x\) 变小的情况下，对于 \(x = \prod_{i=1}^k p_i^{c_i}\)（\(p_i\ \operatorname{为质数}\)）中的 \(c_i\) 至少有 \(1\) 个 \(c_i\leftarrow m\)（\(m < c_i, p_i^{m+1}\not\mid i\)），则 \(1 + \sum_{i+1}^k c_i\)（注意还有 \(x = 1\) 的情况）即为取值数量上限，不难证出上限即为 \(\log_2(x) + 1\)
考虑对于节点 \(u\)，\(u\leftarrow fa_u\) 并 \(sum\leftarrow \gcd(sum, v_{fa_u})\)（\(sum = v_u\)）这个操作，\(sum\) 个数上限为 \(\log_2(sum) + 1\)
那就可以直接用一个 map \(cnt_u\) 存储 \(sum\) 出现的值和出现次数，对于 \(u\) 就可以直接从 \(cnt_{fa_u}\) 推出 \(cnt_u\)
时间复杂度 \(O(n\log^2_2 n)\)
#include<bits/stdc++.h>
using namespace std;
#define int64 long long
const int64 mod = 1e9 + 7;
const int N = 100000 + 20;
struct Line {
int v, nxt;
#define v(i) l[i].v
#define nxt(i) l[i].nxt
} l[N * 2];
int head[N], lcnt;
void add(int u, int v) {
l[++lcnt] = {v, head[u]}; head[u] = lcnt;
return ;
}
int64 v[N];
map<int64, int> cnt[N];
int64 ans;
void dfs(int u, int fa) {
cnt[u][v[u]]++;
for (map<int64, int>::iterator it = cnt[fa].begin(); it != cnt[fa].end(); it++) {
cnt[u][__gcd((*it).first, v[u])] += (*it).second;
}
for (map<int64, int>::iterator it = cnt[u].begin(); it != cnt[u].end(); it++) {
ans = (ans + (*it).first * (int64)((*it).second) % mod) % mod;
}
for (int i = head[u]; i; i = nxt(i)) {
if (v(i) == fa) {
continue;
}
dfs(v(i), u);
}
return ;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &v[i]);
}
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v); add(v, u);
}
dfs(1, 0);
printf("%lld", ans);
return 0;
}