思路：直接用求(b,1)范围内互质的数，(a-1,1)范围内互质的数。再求反
就是敲一下容斥模板
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<queue> 5 #include<stack> 6 #include<algorithm> 7 using namespace std; 8 #define clc(a,b) memset(a,b,sizeof(a)) 9 #define inf 0x3f3f3f3f 10 const int N=10010; 11 #define LL long long 12 // inline int r(){ 13 // int x=0,f=1;char ch=getchar(); 14 // while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();} 15 // while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 16 // return x*f; 17 // } 18 19 int T; 20 LL a,b,n; 21 int pri[110]; 22 int k; 23 void fun(LL x){ 24 k=0; 25 for(int i=2;i*i<=x;i++){ 26 if(x&&x%i==0){ 27 pri[k++]=i; 28 while(x&&x%i==0){ 29 x/=i; 30 } 31 } 32 } 33 if(x>1) pri[k++]=x; 34 } 35 LL exclu(LL num,int m){ 36 LL ans=0,tmp,times; 37 for(int i=1;i<(LL)(1<<m);i++){ 38 tmp=1,times=0; 39 for(int j=0;j<m;j++){ 40 if(i&((LL)(1<<j))) 41 times++,tmp*=pri[j]; 42 } 43 if(times&1) ans+=num/tmp; 44 else ans-=num/tmp; 45 } 46 return ans; 47 } 48 int main(){ 49 scanf("%d",&T); int cas=1; 50 while(T--){ 51 scanf("%I64d%I64d%I64d",&a,&b,&n); 52 clc(pri,0); 53 fun(n); 54 LL ans1=exclu(a-1,k); 55 LL ans2=exclu(b,k); 56 printf("Case #%d: %I64d ",cas++,b-ans2-(a-1-ans1)); 57 } 58 return 0; 59 }