这个思路还是很巧妙的（其实就是转化为二进制，不知道是不是板子，收藏一下）
#include <set> #include <map> #include <queue> #include <stack> #include <math.h> #include <vector> #include <string> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <algorithm> #define zero(a) fabs(a)<eps #define lowbit(x) (x&(-x)) #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define MOD 1000000007 int max(int x,int y){return x>y?x:y;}; int min(int x,int y){return x<y?x:y;}; int max(int x,int y,int z){return max(x,max(y,z));}; int min(int x,int y,int z){return min(x,min(y,z));}; typedef long long LL; const double PI=acos(-1.0); const double eps=1e-8; const int inf=0x3f3f3f3f; const LL linf=0x3f3f3f3f3f3f3f3fLL; using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int prime[33],pn; LL calc(LL n) { LL res=0; for(int i=1;i<(1<<pn);i++){ int tmp=1,cnt=0; for(int j=0;j<pn;j++){ if(((i>>j)&1)==0)continue; ++cnt; tmp*=prime[j]; } if(cnt&1)res+=n/tmp; else res-=n/tmp; } return n-res; } int main() { LL a,b; int T,n; scanf("%d",&T); int cas=1; while(T--){ scanf("%lld%lld%d",&a,&b,&n); pn=0; for(int i=2;i*i<=n;i++){ if(n%i)continue; while(n%i==0)n/=i; prime[pn++]=i; } if(n!=1)prime[pn++]=n; printf("Case #%d: %lld ",cas++,calc(b)-calc(a-1)); } }