# Codeforces 1229B Kamil and Making a Stream()-其他

## Codeforces 1229B Kamil and Making a Stream()

$$\gcd$$ 一个性质：对于正整数 $$x$$， 重复 $$x\leftarrow \gcd(x, i)$$（$$i\ge 0$$）直到 $$x = 1$$，$$x$$ 出现的值个数上限为 $$\log_2(x)+1$$

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];
void add(int u, int v) {
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);
}
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$$

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];
void add(int u, int v) {
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);