HDU4135 Co-prime（容斥原理）

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 int prime[33],pn;
 5 long long calc(long long n){
 6     long long res=0;
 7     for(int i=1; i<(1<<pn); ++i){
 8         int tmp=1,cnt=0;
 9         for(int j=0; j<pn; ++j){
10             if(((i>>j)&1)==0) continue;
11             ++cnt;
12             tmp*=prime[j];
13         }
14         if(cnt&1) res+=n/tmp;
15         else res-=n/tmp;
16     }
17     return n-res;
18 }
19 int main(){
20     long long a,b;
21     int t,n;
22     scanf("%d",&t);
23     for(int cse=1; cse<=t; ++cse){
24         scanf("%lld%lld%d",&a,&b,&n);
25         pn=0;
26         for(int i=2; i*i<=n; ++i){
27             if(n%i) continue;
28             while(n%i==0) n/=i;
29             prime[pn++]=i;
30         }
31         if(n!=1) prime[pn++]=n;
32         printf("Case #%d: %lld\n",cse,calc(b)-calc(a-1));
33     }
34     return 0;
35 }