Codeforces 1229B Kamil and Making a Stream()

\(\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\)
那就可以直接用一个 \(cnt_u\) 存储 \(sum\) 出现的值和出现次数，对于 \(u\) 就可以直接从 \(cnt_{fa_u}\) 推出 \(cnt_u\)
时间复杂度 \(O(n\log^2_2 n)\)

map
#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;
}
————————

\(\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\)
那就可以直接用一个 \(cnt_u\) 存储 \(sum\) 出现的值和出现次数，对于 \(u\) 就可以直接从 \(cnt_{fa_u}\) 推出 \(cnt_u\)
时间复杂度 \(O(n\log^2_2 n)\)

map
#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;
}