文章目录

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4135
如果是求某一个n互质的个数的话，那确实是这样容斥比较好
原理也感觉比较简单，要找与n互质那就是要找，那就减去不互质的个数不就行了，于是就把n的质因子找出来，那么质因子的倍数就肯定与n不互质，然后就容斥。

容斥有dfs，和位运算枚举出来，而今天学到了一个直接用队列数组容斥出来的，哇感觉很爽~
参考这位大佬的博客：https://www.cnblogs.com/jiangjing/archive/2013/06/03/3115470.html

#include"bits/stdc++.h"
#define out(x) cout<<#x<<"="<<x
#define C(n,m) (m>n?0:(long long)fac[(n)]*invf[(m)]%MOD*invf[(n)-(m)]%MOD)
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
LL L,R,N;
int t;
int prime[maxn];
int que[maxn];
LL solve(LL n)//求n以内与N不互质的个数 
{
	LL ans=0;
	for(int i=2; i<=t; i++)
	{
		ans+=n/que[i];
	}
	return ans;
}
int main()
{
	int T;
	cin>>T;
	for(int Case=1; Case<=T; Case++)
	{
		cin>>L>>R>>N;
		LL n=N;
		int cnt=0;
		for(LL i=2; i*i<=n; i++)
		{
			if(n%i==0)
			{
				while(n%i==0)n/=i;
				prime[++cnt]=i;
			}
		}
		if(n>1)prime[++cnt]=n;
		t=0;
		que[++t]=-1;
		for(int i=1; i<=cnt; i++)//用队列数组进行容斥 
		{
			int len=t;
			for(int k=1; k<=len; k++)que[++t]=que[k]*prime[i]*(-1);
		}
		cout<<"Case #"<<Case<<": "<<R-L+1-(solve(R)-solve(L-1))<<endl;

	}
}