1 #include <iostream> 2 using namespace std; 3  4 long long Prime[50];//存放N的质因子 5  6  7 long long getNonCoPrime(long long num,int m)//计算非互质数的多少 8 { 9     long long ans=0,flag,temp;10     for(long long i =1;i<(long long)(1<<m);i++)//用二进制串来表示每个质因子是否被取11     {12         temp = 1;13         flag = 0;14         for(int j = 0;j<m;j++)//判断每位是否取到15         {16             if(i&((long long)(1<<j)))//如果取了17             {18                 flag++;19                 temp*=Prime[j];20             }21         }22         if(flag&1)//容斥原理 ，奇加偶减 23         {24                 ans+=num/temp;25         }else{26             ans-=num/temp;27         }28         29     }30     return ans;31 }32 33 34 int main()35 {36     int T;37     cin>>T;38     int t =T;39     40     while(T--)41     {42         long long A,B;43         int N;44         cin>>A>>B>>N;45         int j =0;46         for(int i = 2;i*i<=N;i++)//获得质因子47         {48             if(N&&N%i==0)49             {50                 Prime[j]=i;51                 j++;52                 while(N&&N%i==0)//避免重复53                 {54                     N/=i;55                 }56             }57         }58         if(N>1)59             Prime[j++]=N;60         long long result = B-A-(getNonCoPrime(B,j) -getNonCoPrime(A-1,j))+1;61         cout<<"Case #"<<t-T<<": "<<result<<endl;62     }63     return 0;64 }