题目大意就是求[l,r]和n互质的数的个数
做法就是反着求，求不和n互质的数的个数，然后相减即可。先把n分解出质因数存在数组里，每个质因数在[l,r]内的倍数组成一个集合该集合里的数就是和n不互质的数，我们把全部集合里的元素个数加起来，会有重复出现，那么就要用容斥定理去做到不重不漏的统计区间里不和n互质的数的个数.
#include<bits/stdc++.h>
using namespace std;
int zys[10000],num,t,n;
long long a,b;
void findzys(int x) //求x的质因子
{
num = 0;
for (int i = 2 ; i * i <= x ; i++)
{
if (x % i == 0)
{
zys[num++] = i;
while (x % i == 0)
x /= i;
}
}
if (x > 1)
zys[num++] = x;
}
long long solve(long long x)//在1到x范围里找不和n互质的数有多少个
{
if(x==0) return 0;
long long ans=0;
for(long long i=1;i<((long long)(1<<num));i++)//把num个质因数的状态都枚举一遍
{
long long t=1;
int cnt=0;//记录这个状态操作了多少个质因数
for(int j=0;j<num;j++)
{
if(i&(long long)(1<<j))
{
cnt++;
t*=zys[j];
}
}
if(cnt&1)
ans+=x/t;
else
ans-=x/t;
}
return ans;
}
int main()
{
int mycase=1;
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld%d",&a,&b,&n);
findzys(n);
printf("Case #%d: %lld ",mycase,b-a+1-(solve(b)-solve(a-1)));
mycase++;
}
return 0;
}