HDU4135容斥原理

 1 #include <cstdio>
 2 #include <string.h>
 3 #include <cmath>
 4 
 5 using namespace std;
 6 
 7 #define MAXSIZE 40000
 8 #define LL long long
 9 int prim[MAXSIZE];
10 LL A,B,n,odd,even;
11 int k;//k记录素数的个数
12 
13 
14 void findPrim(LL n)
15 {
16     k=0;
17     for(int i=2; i*i<=n; i++) //对n进行素因子分解
18     {//筛法求素数
19         if(n%i==0)
20         {
21             prim[k++]=i;
22             while(n%i==0)
23                 n/=i;
24         }
25     }
26     if(n>1)
27         prim[k++]=n;
28 }
29 
30 void getCount(int N)
31 {
32     long long mul=1;
33     int count=0;
34     int m=0;
35     while(N){
36         if(N&1) {
37             count++;
38             mul*=prim[m];
39         }
40         m++;
41         N>>=1;
42     }
43     long long t=B/mul-(A-1)/mul;
44     if(count%2==0) even+=t;
45     else odd+=t;
46 }
47 
48 int main()
49 {
50     int T,log;
51     scanf("%d",&T);
52     for(int x=1;x<=T;x++)
53     {
54         odd=0,even=0,log=1;
55         scanf("%I64d%I64d%I64d",&A,&B,&n);
56         findPrim(n);
57 
58         /*for(int i=0;i<k;i++) printf("%d ",prim[i]);
59         printf("
");*/
60 
61         while(log<(1<<k)){
62             getCount(log);
63             log++;
64         }
65         printf("Case #%d: ",x);
66         printf("%I64d
",B-A+1-odd+even);
67     }
68     return 0;
69 }