Codeforces - GCD Counting

题目链接：Codeforces - GCD Counting

显然，做法很多。

我就直接点分治暴力了。

每次分治重心，然后对每个数，分解质因数。对重心的每个质因数都求一下答案，取max即可。

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10;
int n,a[N],mx,sum,sz[N],vis[N],rt,q[N],res,dep1,dep2,maxd,st[N];
vector<int> g[N],prime[N];
inline void add(int a,int b){g[a].push_back(b),g[b].push_back(a);}
void get_prime(int n){
for(int i=2;i<=n;i++)	if(!st[i]){
prime[i].push_back(i);
for(int j=2*i;j<=n;j+=i)	prime[j].push_back(i),st[j]=1;
}
}
void get(int x,int fa){
sz[x]=1; int t=0;
for(auto to:g[x]){
if(vis[to]||to==fa)	continue;
get(to,x); sz[x]+=sz[to]; t=max(t,sz[to]);
}
t=max(t,sum-sz[x]); if(t<mx)	mx=t,rt=x;
}
void getdis(int x,int fa,int h,int val){
if(__gcd(a[x],val)!=val)	return ;
maxd=max(maxd,h);
for(auto to:g[x]){
if(to==fa||vis[to])	continue;
getdis(to,x,h+1,val);
}
}
void calc(int x,int val){
dep1=dep2=0;
for(auto to:g[x]){
if(vis[to])	continue;
maxd=0;	getdis(to,x,1,val);
if(maxd>dep1)	dep2=dep1,dep1=maxd;
else if(maxd>dep2)	dep2=maxd;
}
res=max(res,dep1+dep2+1);
}
void divide(int x){
vis[x]=1;
for(int i=0;i<prime[a[x]].size();i++)	calc(x,prime[a[x]][i]);
for(auto to:g[x]){
if(vis[to])	continue;
mx=sum=sz[to]; get(to,x);
divide(rt);
}
}
signed main(){
cin>>n;	get_prime(2e5);
for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
for(int i=1,a,b;i<n;i++)	scanf("%d %d",&a,&b),add(a,b);
mx=sum=n; get(1,0); divide(1);
cout<<res;
return 0;
}

最后

以上就是痴情裙子为你收集整理的Codeforces - GCD Counting的全部内容，希望文章能够帮你解决Codeforces - GCD Counting所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。