【题解】CF990G GCD Counting

CF990G GCD Counting

\(\text{Solution:}\)

考虑一个 naive 的想法，首先直接枚举答案 \(i,\) 然后把所有是 \(i\) 的倍数的点全部拉出来，这样它们就会组成一些连通块。

依次统计其路径条数，那么这些就是 \(i|\gcd\) 的答案。

那么设 \(f(i)\) 表示我们算出来的答案，设 \(F(i)\) 表示我们想要的答案。

那么此时显然有 \(f(i)=\sum_{i|d} F(d)\)

直接考虑一波反演，\(F(i)=\sum_{i|d}\mu(\frac{d}{i})f(d)\) 即可。

这里有一些学习到的小技巧以及注意事项：

首先是如何把所有点拉出来形成连通块：直接维护点的话发现再枚举连接它的边复杂度就炸了，所以考虑直接找边。对于一条边，求其端点的 \(\gcd,\) 然后暴力找其因数记录编号即可。

连边可以用并查集维护一下 \(siz\)

然后注意莫反的时候要用到所有是它倍数的点的答案，所以不要因为这个点的实际答案是 \(0\) 就直接不去计算，这样会导致反演出错

还有，注意到 \(256M\) 的空间一定要留意，这题一旦 #define int long long 就直接炸空间了

#include
using namespace std;
typedef double db;
//#define int long long
const int mod=1e9+7;
const db eps=1e-10;
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return xeps?x:y;}
inline db Min(db x,db y){return x-y pii;
#define fi first
#define se second
#define mk make_pair
#define pb emplace_back
#define poly vector
#define Bt(a) bitset
#define bc __builtin_popcount
#define pc putchar
#define ci const int&
inline int Abs(int x){return x<0?-x:x;}
//char buf[1<<21],*p1=buf,*p2=buf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char Obuf[1<<21],*O=Obuf;//Siz shoule be the size of Out File
//int pst[30],ptop;
//inline void Fwrite(int x){
//	if(x<0)*O++='-',x=-x;ptop=0;
//	while(x)pst[++ptop]=x%10,x/=10;
//	while(ptop)*O++=pst[ptop--]+'0';
//}
//inline void Fprint(){fwrite(Obuf,1,O-Obuf,stdout);}
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
inline void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
inline int qpow(int x,int y){
	int res=1;
	while(y){
		if(y&1)res=Mul(res,x);
		x=Mul(x,x);y>>=1;
	}
	return res;
}
inline void cadd(int &x,int y){x+=y;}
inline void cmul(int &x,int y){x*=y;}
inline void cmax(int &x,int y){x=Max(x,y);}
inline void cmin(int &x,int y){x=Min(x,y);}
const int N=2e5+10;
namespace Refined_heart{
	int a[N],n,siz[N],vvis[N],pr[N],cntt,mu[N];
	long long g[N];
	struct E{int u,v;}edge[N];
	inline void pred(){
		mu[1]=1;
		for(int i=2;i<=200000;++i){
			if(!vvis[i])pr[++cntt]=i,mu[i]=-1;
			for(int j=1;j<=cntt&&pr[j]*i<=200000;++j){
				vvis[i*pr[j]]=1;
				if(i%pr[j]==0)break;
				mu[i*pr[j]]=-mu[i];
			}
		}
	}
	inline int gcd(int x,int y){return !y?x:gcd(y,x%y);}
	poly d[N];
	int node[N],rec[N],rcnt;
	int f[N],vis[N],V[N],ans[N];
	inline int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
	inline void merge(int x,int y){
		int fx=find(x);
		int fy=find(y);
		if(fx==fy)return;
		f[fx]=fy;siz[fy]+=siz[fx];
	}
	void solve(){
		n=read();
		for(int i=1;i<=n;++i)a[i]=read(),node[a[i]]++,siz[i]=1,f[i]=i;
		for(int i=1;i