正题

题目链接:https://www.luogu.com.cn/problem/CF990G

题目大意

给出一棵有点权的树，对于每个\(k\)求有多条路径的点权\(gcd\)为\(k\)

\(1\leq n\leq 2\times 10^5,1\leq a_i\leq 2\times 10^5\)

解题思路

开始以为要莫反，后来发现不用。

首先\(gcd\)之间拆倍数，设\(f_i\)表示点权都是\(i\)的倍数的路径条数，这个用一个\(vector\)存然后暴力枚举\(i\)加点每次\(dfs\)出每个联通块的大小就好了。

之后倒序枚举\(i\)，再枚举它的倍数\(ik\)，然后\(f_i-=f_{ik}\)，这样就自动容斥，用不上莫比乌斯反演了。

时间复杂度\(O(\sum_{i=1}^n\sigma_0(a_i)+n\log n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define ll long long

using namespace std;

const ll N=2e5+10;

ll n,w[N],v[N],f[N];

vector<ll> p[N],G[N];

//void Prime(){

//	mu[1]=1;

//	for(ll i=2;i<N;i++){

//		if(!v[i])v[i]=1,pri[++cnt]=i,mu[i]=-1;

//		for(ll j=1;j<=cnt&&i*pri[j]<N;j++){

//			v[i*pri[j]]=1;

//			if(i%pri[j]==0)break;

//			mu[i*pri[j]]=-mu[i];

//		}

//	}

//	return;

//}

ll Add(ll x,ll fa,ll k){

	v[x]=k;ll siz=0;

	for(ll i=0;i<G[x].size();i++){

		ll y=G[x][i];

		if(y==fa||w[y]%k)continue;

		siz+=Add(y,x,k);

	}

	return siz+1;

}

signed main()

{

	scanf("%lld",&n);

	for(ll i=1;i<=n;i++){

		scanf("%lld",&w[i]);

		p[w[i]].push_back(i);

	}

	for(ll i=1;i<n;i++){

		ll x,y;

		scanf("%lld%lld",&x,&y);

		G[x].push_back(y);

		G[y].push_back(x);

	}

	for(ll i=1;i<=2e5;i++)

		for(ll j=i;j<=2e5;j+=i)

			for(ll k=0;k<p[j].size();k++){

				ll x=p[j][k];

				if(v[x]==i)continue;

				ll siz=Add(x,x,i);

				f[i]+=siz*(siz+1)/2;

			}

	for(ll i=2e5;i>=1;i--)

		for(ll j=2*i;j<=2e5;j+=i)

			f[i]-=f[j];

	for(ll i=1;i<=2e5;i++)

		if(f[i])printf("%lld %lld\n",i,f[i]);

	return 0;

}

巴特西

CF990G-GCD Counting【dfs】

正题

题目大意

解题思路

code

最新文章

热门文章