正題

題目鏈接:https://www.luogu.com.cn/problem/CF990G

---

題目大意

給出一棵有點權的樹，對于每個$k$求有多條路徑的點權$gcd$為$k$

$1\le n\le 2\times 10^5,1\le a_i\le 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】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。