最近学习容斥原理，实现容斥原理大致有三种方法：dfs，队列数组，二进制。

今天主要讲下二进制实现容斥原理：

   有一个集合{A1……An}，求集合的子集？很显然答案为

也就是2^n个，也就是每一个子集有唯一标志符 i (0<i<2^n,空集除外),也就是说有唯一的二进制表示！

代码看下面的：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 using namespace std;10 int prime[40000],m;11 bool f[40000];12 vector
             
              p;//存放质因数13 //用筛法初始化40000以内的质数，将质数存放在prime数组中，m记录大小14 int init(){15 m=0;16 for(int i=2; i<40000; i++){17 if (f[i]==0) prime[m++]=i;//质数18 //筛去合数19 for (int j=0; j
              
               <40000; j++){20 f[i*prime[j]]=1;21 if (i%prime[j]==0) break;//保证每个数只筛去一次22 }23 }24 }25 //对n分解质因数26 void factor(int n){27 p.clear();28 for (int i=0; i
               
                <=n; i++){29 if (n%prime[i]==0){30 p.push_back(prime[i]);31 n/=prime[i];32 while (n%prime[i]==0)33 n/=prime[i];34 }35 }36 if(n>1) p.push_back(n);37 }38 //用二进制实现容斥原理,求区间[1,r]内与n互素的数的个数39 int solve(int r){40 int sum = 0;41 //i的范围是1-2^p.size()，空集除外，每一个子集所对应的42 //二进制都不一样，也就是i43 for (int i=1; i<(1<
                
                 >n>>r){61 factor(n);62 cout<
                 
                  <