【CF1210C】Kamil and Making a Stream（vector，数论，树）

题意：给定一棵n个点带点权的树，i号点的点定义f(i,j)为i到j路径上所有点的gcd，其中i是j的一个祖先，求所有f(i,j)之和mod1e9+7

2<=n<=1e5，0<=a[i]<=1e12

思路：从根往下直接暴力跑，每个点开个vector继承父节点的信息，取gcd之后再把值相等的合并

大胆猜想，不用求证

注意0还是要保留的

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 typedef unsigned int uint;
  5 typedef unsigned long long ull;
  6 typedef pair<int,int> PII;
  7 typedef pair<ll,ll> Pll;
  8 typedef vector<int> VI;
  9 typedef vector<PII> VII;
 10 typedef pair<ll,ll>P;
 11 #define N  200010
 12 #define M  200010
 13 #define fi first
 14 #define se second
 15 #define MP make_pair
 16 #define pi acos(-1)
 17 #define mem(a,b) memset(a,b,sizeof(a))
 18 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
 19 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
 20 #define lowbit(x) x&(-x)
 21 #define Rand (rand()*(1<<16)+rand())
 22 #define id(x) ((x)<=B?(x):m-n/(x)+1)
 23 #define ls p<<1
 24 #define rs p<<1|1
 25  
 26 const ll MOD=1e9+7,inv2=(MOD+1)/2;
 27       double eps=1e-4;
 28       int INF=1<<30;
 29       ll inf=5e13;
 30       int dx[4]={-1,1,0,0};
 31       int dy[4]={0,0,-1,1};
 32  
 33 int head[N],vet[N],nxt[N],fa[N],d[N],vis[N],tot;
 34 ll a[N],ans;
 35 P b[N];
 36 vector<P> c[N];
 37  
 38 int read()
 39 {
 40    int v=0,f=1;
 41    char c=getchar();
 42    while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
 43    while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
 44    return v*f;
 45 }
 46  
 47 void add(int a,int b)
 48 {
 49     nxt[++tot]=head[a];
 50     vet[tot]=b;
 51     head[a]=tot;
 52 }
 53  
 54 ll gcd(ll x,ll y)
 55 {
 56     if(!y) return x;
 57     return gcd(y,x%y);
 58 }
 59  
 60 void dfs(int u,int fa)
 61 {
 62     //printf("u=%d fa=%d
",u,fa);
 63     if(fa)
 64     {
 65         for(int i=0;i<c[fa].size();i++) c[u].push_back(c[fa][i]);
 66         //c[u]=c[fa];
 67     }
 68  
 69     for(int i=0;i<c[u].size();i++) c[u][i].fi=gcd(c[u][i].fi,a[u]);
 70     int m=0;
 71     for(int i=0;i<c[u].size();i++) b[++m]=c[u][i];
 72     sort(b+1,b+m+1);
 73     c[u].clear();
 74     rep(i,1,m)
 75     {
 76         int now=(int)c[u].size()-1;
 77         if(now==-1||b[i].fi!=c[u][now].fi) c[u].push_back(b[i]);
 78          else c[u][now].se=(c[u][now].se+b[i].se)%MOD;
 79     }
 80     c[u].push_back(MP(a[u],1));
 81     for(int i=0;i<c[u].size();i++) ans=(ans+c[u][i].fi%MOD*c[u][i].se%MOD)%MOD;
 82     int e=head[u];
 83     while(e)
 84     {
 85         int v=vet[e];
 86         if(v!=fa) dfs(v,u);
 87         e=nxt[e];
 88     }
 89     //printf("u=%d fa=%d ans=%I64d
",u,fa,ans);
 90 }
 91  
 92  
 93  
 94 int main()
 95 {
 96     //freopen("1.in","r",stdin);
 97     int n=read();
 98     rep(i,1,n) scanf("%I64d",&a[i]);
 99     tot=0;
100     rep(i,1,n) head[i]=0;
101     rep(i,1,n-1)
102     {
103         int x=read(),y=read();
104         add(x,y);
105         add(y,x);
106     }
107     dfs(1,0);
108     printf("%I64d
",ans);
109     return 0;
110 }