前言

萌新做了下 CF1750 D\text{CF1750 D} 发现自己对容斥的理解完全不深入

容斥，顾名思义，就是分别算每个的贡献，然后减去重复的贡献。

我们考虑容斥的应用。

应用

求 [1,m][1,m] 满足 gcd⁡(x,n)=1\gcd(x,n)=1 的个数

显然，我们考虑唯一分解定理， n=p1k1∗p2k2∗p3k3∗...∗pnknn=p_1^{k_1}*p_2^{k_2}*p_3^{k_3}*...*p_n^{k_n}

我们考虑 ki>0k_i>0 的情况

换句话说 nn 不能是 pip_i 的倍数，这显然就是一个容斥原理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
mmp=tmp;
tmp=a[i];
int sz=0,d[30]={0};
for(int j=1;p[j]*p[j]<=mmp;j++)
{
	if(mmp%p[j]==0) 
	{
	d[++sz]=p[j],mmp/=p[j];
	while(mmp%p[j]==0) mmp/=p[j];
   }
}
if(mmp>1) d[++sz]=mmp;
int aans=0;
for(int s=1;s<=(1<<sz)-1;s++)
{
	int lk=1;
	int cc=0;
	for(int j=1;j<=sz;j++)
	{
		if(1<<(j-1)&s) lk*=d[j],cc++;
	}
    aans+=(m-m/lk)*((cc&1)?1:-1);
}
ans=(1ll*ans*aans)%modp;