数学：容斥原理

容斥原理ACM必考！！！！！！

容斥原理小学的时候就学过但是，这里考察容斥原理可不是画一画韦恩图就完事了

归根到底就是一句话，加上奇数个集合的并，减去偶数个集合的并

例题BZOJ2393

题意是这样的，给定一个范围，然后让你算一下有多少个数能被一种神奇的数组成

这种神奇的数只有2和9构成

首先预处理出1~r以内所有只由2和9构成的baka数容易发现最多有1022个

但是其中有一些baka数是另一些的倍数

我们把较大的抛去，只剩下小的，这样baka数就变成了500多个

然后就是求区间内这些数的倍数的数的数量

总数=是一个数的倍数的数的数量-是两个数公倍数的数的数量+是三个数公倍数的数的数量……

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=2005;
 6 int l,r,t,m,n,ans;
 7 bool vis[maxn];
 8 int a[maxn],b[maxn];
 9 long long gcd(long long a,long long b)
10 {
11     return b==0?a:gcd(b,a%b);
12 }
13 void pre(int x,int y)
14 {
15     if(x>t||y>r) return;
16     if(x>0) a[++m]=y;
17     pre(x+1,y*10+2);
18     pre(x+1,y*10+9);
19 }
20 void dfs(int x,int y,long long z)
21 {
22     if(x>n)
23     {
24         if(y&1) ans+=r/z-(l-1)/z;
25         else if(y) ans-=r/z-(l-1)/z;
26         return;
27     }
28     dfs(x+1,y,z);
29     long long next=a[x]*z/gcd(a[x],z);
30     if(next<=r) dfs(x+1,y+1,next);
31 }
32 int main()
33 {
34     scanf("%d%d",&l,&r);
35     t=(int)(log(r)/log(10))+1;
36     pre(0,0);
37     sort(a+1,a+m+1);
38     for(int i=1;i<=m;i++)
39     {
40         if(!vis[i])
41         {
42             b[++n]=a[i];
43             for(int j=i+1;j<=m;j++)
44                 if(a[j]&a[i]==0) vis[j]=1;
45         }
46     }
47     for(int i=1;i<=n;i++)
48         a[n-i+1]=b[i];
49     dfs(1,0,1);
50     printf("%lld",ans);
51     return 0;
52 }

逻辑题还要多写