/*
树上莫比乌斯反演
求树上 满足 d|gcd(au,av) gcd(au,av)的对数f(d)
如何求：
建立200000层新图，即对于每个数建立一个新图
在加边时，给gcd(au,av)的约数层的图的uv加边
f[i]表示第i层的满足条件 i | gcd(a[u],a[v]) 的对数,那么求一遍并查集，在合并过程中更新f[i]即可，
同时要注意f[i]初始值为这层的有效结点数量，对应i|gcd(a[u],a[u])这样的情况
然后用莫比乌斯反演来求最后答案g[d]=sigma(u[i]*f[i*d])
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
int phi[maxn],mu[maxn],prime[maxn],m;
bool vis[maxn];
void init(){
//打表mu
phi[
1]=mu[
1]=
1;
for(
int i=
2;i<maxn;i++
){
if(!
vis[i]){
mu[i]=-
1;prime[++m]=i;phi[i]=i-
1;
}
for(
int j=
1;j<=m;j++
){
if(i*prime[j]>=maxn)
break;
vis[i*prime[j]]=
1;
if(i%prime[j]==
0){
phi[i*prime[j]]=phi[i]*
prime[j];
mu[i*prime[j]]=
0;
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-
1),mu[i*prime[j]]=-
mu[i];
}
}
}
int n,a[maxn];
long long f[maxn],u[maxn],v[maxn];
vector<
int>vec[maxn];
//每层的边的下标集合
int F[maxn],size[maxn];
int find(
int x){
return F[x]==x?x:F[x]=
find(F[x]);
}
void bing(
int i,
int u,
int v){
int t1=find(u),t2=
find(v);
if(t1==t2)
return;
f[i]+=(
long long)size[t1]*
size[t2];
size[t1]+=size[t2];F[t2]=
t1;
}
int main(){
init();
cin>>
n;
for(
int i=
1;i<=n;i++
){
cin>>
a[i];
for(
int j=
1;j*j<=a[i];j++
)
if(a[i]%j==
0){
f[j]++
;
if(a[i]/j!=j)f[a[i]/j]++
;
}
}
for(
int i=
1;i<n;i++){
//建立2000000层新图
scanf(
"%d%d",&u[i],&
v[i]);
int tmp=
__gcd(a[u[i]],a[v[i]]);
for(
int j=
1;j*j<=tmp;j++
)
if(tmp%j==
0){
vec[j].push_back(i);
if(tmp/j!=
j)
vec[tmp/
j].push_back(i);
}
}
//求并查集
for(
int i=
1;i<=
200000;i++
){
for(
int j=
0;j<vec[i].size();j++){
//先初始化每层对应的并查集
int uu=u[vec[i][j]],vv=
v[vec[i][j]];
F[uu]=uu;F[vv]=
vv;
size[uu]=
1;size[vv]=
1;
}
for(
int j=
0;j<vec[i].size();j++){
//再进行合并求值
int uu=u[vec[i][j]],vv=
v[vec[i][j]];
bing(i,uu,vv);
}
}
//反演+输出
for(
int d=
1;d<=
200000;d++
){
long long ans=
0;
for(
int i=
1;i*d<=
200000;i++
)
ans+=(
long long)mu[i]*f[i*
d];
if(ans!=
0)
cout<<d<<
" "<<ans<<
'\n';
}
}
转载于:https://www.cnblogs.com/zsben991126/p/11117356.html
相关资源：各显卡算力对照表！
