CodeForces - 990G GCD Counting

Discription

You are given a tree consisting of nn vertices. A number is written on each vertex; the number on vertex ii is equal to aiai.

Let's denote the function g(x,y)g(x,y) as the greatest common divisor of the numbers written on the vertices belonging to the simple path from vertex xx to vertex yy(including these two vertices).

For every integer from 11 to 2⋅1052⋅105 you have to count the number of pairs (x,y)(x,y) (1≤x≤y≤n)(1≤x≤y≤n) such that g(x,y)g(x,y) is equal to this number.

Input

The first line contains one integer nn — the number of vertices (1≤n≤2⋅105)(1≤n≤2⋅105).

The second line contains nn integers a1a1, a2a2, ..., anan (1≤ai≤2⋅105)(1≤ai≤2⋅105) — the numbers written on vertices.

Then n−1n−1 lines follow, each containing two integers xx and yy (1≤x,y≤n,x≠y)(1≤x,y≤n,x≠y)denoting an edge connecting vertex xx with vertex yy. It is guaranteed that these edges form a tree.

Output

For every integer ii from 11 to 2⋅1052⋅105 do the following: if there is no pair (x,y)(x,y) such that x≤yx≤y and g(x,y)=ig(x,y)=i, don't output anything. Otherwise output two integers: iiand the number of aforementioned pairs. You have to consider the values of ii in ascending order.

See the examples for better understanding.

Examples

Input

Output

1 4
2 1
3 1

Input

6
1 2 4 8 16 32
1 6
6 3
3 4
4 2
6 5

Output

Input

Output

1 1
2 1
3 1
6 2
9 2
16 2
144 1

    震惊，玄学做法竟然跑过了点分治。。。。
      很显然，我们可以先求出g是i倍数的点对数ans[i],然后再反演出答案。
    求g是i倍数的点对数的时候就调和级数枚举一下倍数，然后并查集一下就ojbk了。。。

    虽然这种做法对于随机数据来说非常的强大，但是一遇到精心构造的数据就gg了，这就是窝一开始TLE的原因。。。
    比如n个点的点权都是 <=2e5 的约数最多的数，那么上述做法的总运算次数大致是 O((n+m) * div * 反阿科玛函数)，就凉凉了。。。

    后来我加了一个比较强的剪枝就过了：
        当所有点权都是i的倍数的时候，那就不做并查集，而是直接用 C(n+1,2) 减去 >i且是i倍数的J的ans...

    感谢出题人不卡之恩2333

#include<bits/stdc++.h>

#define ll long long

using namespace std;

#define pb push_back

const int maxn=200005;

inline int read(){

	int x=0; char ch=getchar();

	for(;!isdigit(ch);ch=getchar());

	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';

	return x;

}

void W(ll x){ if(x>=10) W(x/10); putchar(x%10+'0');}

int n,m,hd[maxn],ne[maxn*2],to[maxn*2],num,cnt[maxn];

int siz[maxn],dfn[maxn],dc,p[maxn],a[maxn];

vector<int> pt[maxn];

ll ans[maxn];

inline void add(int x,int y){ to[++num]=y,ne[num]=hd[x],hd[x]=num;}

int getf(int x){ return p[x]==x?x:(p[x]=getf(p[x]));}

inline void solve(){

	for(int i=2e5,O;i;i--){

		dc++,O=0;

		for(int j=i;j<=2e5;j+=i) O+=cnt[j],ans[i]-=ans[j];

		if(O==n){

			ans[i]+=n*(ll)(n+1)>>1;

			continue;

		}

		for(int j=i;j<=2e5;j+=i){

			for(int l=pt[j].size()-1,now;l>=0;l--){

				now=pt[j][l];

				if(dfn[now]!=dc) dfn[now]=dc,p[now]=now,siz[now]=1,ans[i]++;

				for(int k=hd[now],fa,fb;k;k=ne[k]) if(dfn[to[k]]==dc){

					fa=getf(now),fb=getf(to[k]);

					if(fa!=fb){

						p[fb]=fa,ans[i]+=siz[fa]*(ll)siz[fb];

						siz[fa]+=siz[fb];

					}

				}

			}

		}

	}

}

int main(){

//	freopen("data.in","r",stdin);

//	freopen("data.out","w",stdout);

	n=read();

	for(int i=1;i<=n;i++) a[i]=read(),pt[a[i]].pb(i),cnt[a[i]]++;

	int uu,vv;

	for(int i=1;i<n;i++)

	    uu=read(),vv=read(),add(uu,vv),add(vv,uu);

	solve();

	for(int i=1;i<=2e5;i++) if(ans[i]) W(i),putchar(' '),W(ans[i]),puts("");

	return 0;

}

巴特西

CodeForces - 990G GCD Counting

最新文章

热门文章