HDU 4135 Co-prime

Co-prime

Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N.
Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than 1 or, equivalently, if their greatest common divisor is 1. The number 1 is relatively prime to every integer.
Input

The first line on input contains T (0 < T <= 100) the number of test cases, each of the next T lines contains three integers A, B, N where (1 <= A <= B <= 10 ¹⁵) and (1 <=N <= 10 ⁹).

Output

For each test case, print the number of integers between A and B inclusive which are relatively prime to N. Follow the output format below.Sample Input

2
1 10 2
3 15 5

Sample Output

Case #1: 5
Case #2: 10

Hint

In the first test case, the five integers in range [1,10] which are relatively prime to 2 are {1,3,5,7,9}. 
容斥
求[A B]中与n互质的个数  我们只需要求[A B]中和n不互质的个数 
比如sum[B]=[1 B]中和n不互质的个数
结果为B-sum[B]-(A-1-sum[A-1])
我们只需要求出n个质因数  根据容斥公式 A+B+C-A*B-A*C-B*C+A*B*C
用二进制生成子集来计算sum

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<string.h>
 7 #include<set>
 8 #include<vector>
 9 #include<queue>
10 #include<stack>
11 #include<map>
12 #include<cmath>
13 typedef long long ll;
14 typedef unsigned long long LL;
15 using namespace std;
16 const int N=1000000+10;
17 int prime[N];
18 ll a[N];
19 ll b[N];
20 ll t;
21 ll cnt;
22 void _prime(){
23     memset(prime,0,sizeof(prime));
24     for(int i=2;i*i<=N;i++){
25         if(prime[i]==0){
26             a[t++]=i;
27             for(int j=i*i;j<=N;j=j+i)prime[j]=1;
28         }
29     }
30 }
31 void deal(ll n){
32     for(int i=0;i<t&&a[i]*a[i]<=n;i++){
33         if(n%a[i]==0){
34             b[cnt++]=a[i];
35             while(n%a[i]==0)n=n/a[i];
36         }
37     }
38     if(n>1)b[cnt++]=n;
39    // for(int i=0;i<cnt;i++)cout<<b[i]<<" ";
40     //cout<<endl;
41 }
42 ll cal(ll n){
43     ll ans=0;
44     for(ll i=1;i<(ll)(1<<cnt);i++){
45         ll flag=0;
46         ll temp=1;
47         for(int j=0;j<cnt;j++){
48             if(i&(ll)(1<<j)){flag++;temp=temp*b[j];}
49         }
50         if(flag%2==1)ans=ans+n/temp;
51         else
52             ans=ans-n/temp;
53     }
54     return ans;
55 }
56 int main(){
57     int tt;
58     t=0;
59     _prime();
60     scanf("%d",&tt);
61     ll A,B;
62     ll n;
63     int i=0;
64     while(tt--){
65         i++;
66        scanf("%I64d%I64d%I64d",&A,&B,&n);
67        cnt=0;
68        deal(n);
69        //cout<<cal(A-1)<<endl;
70        //cout<<cal(B)<<endl;
71        printf("Case #%d: %I64d
",i,B-cal(B)-A+1+cal(A-1));
72        //cout<<B-cal(B)-A+1+cal(A-1)<<endl;
73     }
74 }