Co-prime HDU - 4135(题解)

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <iostream>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <vector>
 7 #include <string>
 8 #include <utility>
 9 #include <queue>
10 #include <stack>
11 #include <map>
12 const int INF=0x3f3f3f3f;
13 using namespace std;
14 
15 typedef long long LL;
16 LL prime[100005];
17 int num; 
18 
19 void prime_get(LL n) //取素数 
20 {
21     num=0;
22     for(LL i=2;i*i<=n;i++)
23     {
24         if(!(n%i)) prime[num++]=i;
25         while(!(n%i)) n/=i;
26     }
27     if(n>1) prime[num++]=n;
28 }
29 
30 LL reject(LL x,int k) //容斥定理  求出1至X区间与N不互质的数 
31 {
32     LL res=0;
33     for(int i=k;i<num;i++) //在草稿纸上把这个过程展开就知道原理了 
34         res=res+x/prime[i]-reject(x/prime[i],i+1);
35     return res;
36 }
37 
38 int main()
39 {
40     int t;
41     cin>>t;
42     for(int i=1;i<=t;i++)
43     {
44         LL a,b,n;
45         cin>>a>>b>>n;
46         prime_get(n);
47         printf("Case #%d: ",i);
48         cout<<(b-reject(b,0))-(a-1-reject(a-1,0))<<endl;
49     }
50     return 0;
51 }