1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
| #include<bits/stdc++.h> #define REG register using namespace std; inline void read(int& x){ static char c; while(!isdigit(c=getchar()));x=c^48; while(isdigit(c=getchar()))x=(x*10)+(c^48); }
const int N=200005;
int n;
int A[N],mu[N],Prm[N],vis[N],Pcnt;
inline void Euler(){ mu[1]=1; for(REG int i=2;i<=N-5;++i){ if(!vis[i]) Prm[++Pcnt]=i,mu[i]=-1; for(REG int j=1;j<=Pcnt&&i*Prm[j]<=N-5;++j){ vis[i*Prm[j]]=1; if(i%Prm[j]==0) break; mu[i*Prm[j]]=-mu[i]; } } }
long long F[N],G[N];
struct Edge{int v,nxt;}ed[N<<1]; int head[N],cnt; inline void adde(int u,int v){ed[++cnt]=(Edge){v,head[u]},head[u]=cnt;} inline void add(int u,int v){adde(u,v),adde(v,u);}
vector<int> V[N];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int tot,Vis[N];
void dfs(int now,int fa,int d){ ++tot,Vis[now]=1; for(REG int i=head[now];i;i=ed[i].nxt){ int v=ed[i].v; if(v==fa||A[v]%d) continue; dfs(v,now,d); } }
inline void Work(){ Euler(); read(n); for(REG int i=1;i<=n;++i) read(A[i]); for(REG int i=1;i<=n;++i) for(REG int j=1;j*j<=A[i];++j){ if(A[i]%j) continue; V[j].push_back(i); if(j^(A[i]/j)) V[A[i]/j].push_back(i); } for(REG int i=1;i<n;++i){ int u,v;read(u),read(v),add(u,v); } for(REG int i=1;i<=N-5;++i){ for(REG int j=0;j<V[i].size();++j) if(!Vis[V[i][j]]) tot=0,dfs(V[i][j],0,i),G[i]+=1ll*tot*(tot+1)/2; for(REG int j=0;j<V[i].size();++j) Vis[V[i][j]]=0; } for(REG int i=1;i<=N-5;++i) for(REG int j=i;j<=N-5;j+=i) F[i]+=G[j]*mu[j/i]; for(REG int i=1;i<=N-5;++i) if(F[i]) printf("%d %lld\n",i,F[i]); }
int main(){Work();}
|