描述
尽管付出了种种努力，jzp还是得过光棍节。
jzp非常不爽，但也无能为力，只能够哀叹起来他的命运。他想到了一位长者的人生经验：“人的一生，不光要靠自我奋斗，也要考虑历史的进程”。
他终于明白自己只是时运不济，所以又继续开始努力。终于在圣诞节当天把到了妹子。
jzp从此过上了快乐的现充生活，在圣诞节当天，他还和妹子玩起了有趣的游戏：
jzp的家里有一棵非常大的圣诞树，可以看成是一个n个点的无向联通无环图。每个点上都有一个正整数，JZP和妹子每次都会选择树上的一条路径，
这条路径的权值被定义为路径上所有点上数的最大公约数，JZP可以得到这个权值的分数。
JZP玩了一会儿有点腻了，他想知道对于每种可能的权值x，权值为x的不同路径的数量（a到b的路径和b到a的路径算作一种，a到a自身也算作一条路径。）
输入
第一行一个整数n(1<=n<=105)表示圣诞树的大小，点从1开始标号。
接下来一行n个整数用单个空格隔开，第i个表示第i个点上的数。（数都在1到105之间）。
接下来n-1行，每行两个数a和b，表示a和b之间有一条边。
输出
令C(x)表示权值为x的路径的个数。
从小到大输出对于所有C(x)>0的x，输出一行两个数x和C(x)，用空格隔开。
样例输入
20
2 4 2 4 2 4 2 20 20 12 12 12 2 12 2 4 4 2 12 2
1 2
1 3
1 4
2 5
3 6
1 7
6 8
2 9
6 10
5 11
4 12
11 13
10 14
3 15
9 16
7 17
4 18
4 19
16 20
样例输出
2 186
4 16
12 6
20 2 首先考虑将问题转化成计算有多少路径的gcd是k的倍数，然后容斥计算出答案。
注意一条路径的gcd是k的倍数等同于路径每条边gcd的gcd，那么我们预处理出对于每个k有那些边符合要求，就可以计算了。
枚举k，将符合条件的边建出来，可以用个并查集，在合并时顺便计算答案。
需要预处理出每个k的因数，暴力分解会T。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=Next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
typedef long long ll;
const int maxn=;
int first2[maxn],Next2[maxn*],id2[maxn*],tot2;
void AddP(int p,int v) {id2[++tot2]=v;Next2[tot2]=first2[p];first2[p]=tot2;}
int first[maxn],Next[maxn*],id[maxn*],tot;
void AddN(int p,int v) {id[++tot]=v;Next[tot]=first[p];first[p]=tot;}
int n,A[maxn],u[maxn],v[maxn],pa[maxn],sz[maxn],S[maxn<<];
int gcd(int a,int b) {return !b?a:gcd(b,a%b);}
int findset(int x) {return pa[x]==x?x:findset(pa[x]);}
ll ans[maxn],res;
void merge(int a,int b) {
int x=findset(a),y=findset(b);
if(x==y) return;
res+=(ll)sz[x]*sz[y];
sz[x]+=sz[y];pa[y]=x;
}
int main() {
n=read();
rep(i,,n) A[i]=read(),pa[i]=i,sz[i]=;
rep(i,,) for(int j=i;j<=;j+=i) AddP(j,i);
rep(i,,n-) {
u[i]=read();v[i]=read();
int x=gcd(A[u[i]],A[v[i]]);
for(int j=first2[x];j;j=Next2[j]) AddN(id2[j],i);
}
dwn(x,,) {
res=;int cnt=;
ren {
merge(u[id[i]],v[id[i]]);
S[++cnt]=u[id[i]];S[++cnt]=v[id[i]];
}
rep(i,,cnt) pa[S[i]]=S[i],sz[S[i]]=;
ans[x]=res;
for(int j=*x;j<=;j+=x) ans[x]-=ans[j];
}
rep(i,,n) ans[A[i]]++;
rep(i,,) if(ans[i]) printf("%d %lld\n",i,ans[i]);
return ;
}