UNIQUE VISION Programming Contest 2022（AtCoder Beginner Contest 248）G. GCD cost on the tree

subject

n(n<=1e5) A tree at a point , Every point has a little power ai(1<=ai<=1e5),

For two points on the tree s、t, Definition C(s,t)=k×gcd(Ap1​​,Ap2​​,…,Apk​​),

among ,k by s To t The number of vertices of this chain ,p1 Is a point s,pk Is a point t, The middle point is the point on the chain

seek , The answer is right 998244353 modulus

Source of ideas

dls/ Official explanation

Answer key 1（ Inversion ）

According to inversion , consider gcd The contribution of , Then count the multiples of each part's contribution ,

According to the formula , take gcd(a1,...,an) The contribution of ,

  That is, for each factor d, stay d On the path of multiples of , There are phi(d) The contribution of ,

Then the problem turns into , Build tree by factor ,dfs Trees , Contribute to each factor

TIPS

According to the formula , Transposition to get ,

You can get O(nlogn) seek phi Methods , That is, initialization at the beginning phi(n)=n,

When enumerating to a certain pair ( factor , Multiple ) In a relationship , Subtract the factor from the multiple phi value

Code 1

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e5,mod=998244353;
int n,u,v,phi[N],a[N],sz[N],all,ans,cnt;
bool vis[N];
vector<int>e[N],fac[N],h[N];
vector<int>now;
struct edge{
	int u,v;
}f[N];
void dfs(int u,int fa){
	all++;
	vis[u]=1;
	sz[u]=1;
	for(auto &v:e[u]){
		if(v==fa)continue;
		dfs(v,u);
		sz[u]+=sz[v];
	}
}
void dfs2(int u,int fa){
	for(auto &v:e[u]){
		if(v==fa)continue;
		cnt=(cnt+1ll*sz[v]*(all-sz[v])%mod)%mod;
		dfs2(v,u);
	}	
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=M;++i){
		phi[i]=i;
	}
	for(int i=1;i<=M;++i){
		fac[i].push_back(i);
		for(int j=2*i;j<=M;j+=i){
			fac[j].push_back(i);
			phi[j]-=phi[i];
		} 
	}
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		f[i]=edge{u,v};
		int g=__gcd(a[u],a[v]);
		//printf("g:%d\n",g);
		for(auto &w:fac[g]){
			//printf("w:%d i:%d\n",w,i);
			h[w].push_back(i);	
		}
	}
	for(int i=1;i<=M;++i){
		if(!h[i].size())continue;
		now.clear();
		for(auto &w:h[i]){
			u=f[w].u,v=f[w].v;
			e[u].push_back(v);
			e[v].push_back(u);
			//printf("i:%d u:%d <- -> v:%d\n",i,u,v);
			if(!vis[u]){
				now.push_back(u);
				vis[u]=1;
			}
			if(!vis[v]){
				now.push_back(v);
				vis[v]=1;
			}
		}
		for(auto &v:now)vis[v]=0;
		for(auto &v:now){
			if(!vis[v]){
				all=cnt=0;
				dfs(v,-1);
				dfs2(v,-1);
				cnt=(cnt+1ll*all*(all-1)/2%mod)%mod;
				//printf("i:%d phi:%d all:%d cnt:%d\n",i,phi[i],all,cnt);
				ans=(ans+1ll*phi[i]*cnt%mod)%mod;
			}	
		}
		for(auto &v:now){
			e[v].clear();
			vis[v]=0;
		}
	}
	printf("%d\n",ans);
	return 0;
} 

Answer key 2（ A class ）

First, for each factor d, Find out d How many paths are there , Then because it will be heavy ,

remember ans[i] Is exactly the factor d The contribution of , be ans[i] Need to subtract ans[2*i],ans[3*i],..., Subtract the contribution of each multiple

Code 2

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e5,mod=998244353;
int n,u,v,phi[N],a[N],sz[N],all,ans[N],cnt,res;
bool vis[N];
vector<int>e[N],fac[N],h[N];
vector<int>now;
struct edge{
	int u,v;
}f[N];
void dfs(int u,int fa){
	all++;
	vis[u]=1;
	sz[u]=1;
	for(auto &v:e[u]){
		if(v==fa)continue;
		dfs(v,u);
		sz[u]+=sz[v];
	}
}
void dfs2(int u,int fa){
	for(auto &v:e[u]){
		if(v==fa)continue;
		cnt=(cnt+1ll*sz[v]*(all-sz[v])%mod)%mod;
		dfs2(v,u);
	}	
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=M;++i){
		phi[i]=i;
	}
	for(int i=1;i<=M;++i){
		fac[i].push_back(i);
		for(int j=2*i;j<=M;j+=i){
			fac[j].push_back(i);
			phi[j]-=phi[i];
		} 
	}
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		f[i]=edge{u,v};
		int g=__gcd(a[u],a[v]);
		//printf("g:%d\n",g);
		for(auto &w:fac[g]){
			//printf("w:%d i:%d\n",w,i);
			h[w].push_back(i);	
		}
	}
	for(int i=1;i<=M;++i){
		if(!h[i].size())continue;
		now.clear();
		for(auto &w:h[i]){
			u=f[w].u,v=f[w].v;
			e[u].push_back(v);
			e[v].push_back(u);
			//printf("i:%d u:%d <- -> v:%d\n",i,u,v);
			if(!vis[u]){
				now.push_back(u);
				vis[u]=1;
			}
			if(!vis[v]){
				now.push_back(v);
				vis[v]=1;
			}
		}
		for(auto &v:now)vis[v]=0;
		for(auto &v:now){
			if(!vis[v]){
				all=cnt=0;
				dfs(v,-1);
				dfs2(v,-1);
				cnt=(cnt+1ll*all*(all-1)/2%mod)%mod;
				//printf("i:%d phi:%d all:%d cnt:%d\n",i,phi[i],all,cnt);
				ans[i]=(ans[i]+cnt)%mod;
			}	
		}
		for(auto &v:now){
			e[v].clear();
			vis[v]=0;
		}
	}
	for(int i=M;i;--i){
		for(int j=2*i;j<=M;j+=i){
			ans[i]=(ans[i]-ans[j]+mod)%mod;
		}
		res=(res+1ll*i*ans[i]%mod)%mod;
	}
	printf("%d\n",res);
	return 0;
}