数学：容斥原理-补集转化

HDU4135：容斥原理之补集转化

求(a,b)区间于n互质的数的个数

那么我们只要找到区间内与n不互质的数的个数就好了

首先我们将n分解质因数

那么就变成了

是一个质因数的倍数的数的个数 - 是两个质因数的倍数的数的个数 + 是三个质因数的倍数的数的个数......

直接容斥原理就好了

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

当然我们求的是补集，要记得用总数减一下