最近學(xué)習(xí)容斥原理，實現(xiàn)容斥原理大致有三種方法：dfs，隊列數(shù)組，二進制。

今天主要講下二進制實現(xiàn)容斥原理：

?? 有一個集合{A1……An}，求集合的子集？很顯然答案為

也就是2^n個，也就是每一個子集有唯一標志符 i (0<i<2^n,空集除外),也就是說有唯一的二進制表示！

代碼看下面的：

1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<iomanip> 5 #include<cmath> 6 #include<cstring> 7 #include<vector> 8 #include<stdlib.h> 9 using namespace std; 10 int prime[40000],m; 11 bool f[40000]; 12 vector<int>p;//存放質(zhì)因數(shù) 13 //用篩法初始化40000以內(nèi)的質(zhì)數(shù)，將質(zhì)數(shù)存放在prime數(shù)組中，m記錄大小 14 int init(){ 15 m=0; 16 for(int i=2; i<40000; i++){ 17 if (f[i]==0) prime[m++]=i;//質(zhì)數(shù) 18 //篩去合數(shù) 19 for (int j=0; j<m&&i*prime[j]<40000; j++){ 20 f[i*prime[j]]=1; 21 if (i%prime[j]==0) break;//保證每個數(shù)只篩去一次 22 } 23 } 24 } 25 //對n分解質(zhì)因數(shù) 26 void factor(int n){ 27 p.clear(); 28 for (int i=0; i<m&&prime[i]*prime[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 //用二進制實現(xiàn)容斥原理,求區(qū)間[1,r]內(nèi)與n互素的數(shù)的個數(shù) 39 int solve(int r){ 40 int sum = 0; 41 //i的范圍是1-2^p.size()，空集除外，每一個子集所對應(yīng)的 42 //二進制都不一樣，也就是i 43 for (int i=1; i<(1<<p.size()); ++i){ 44 int mult = 1,bits = 0; 45 for (int j=0; j<p.size(); ++j) 46 if (i&(1<<j)){//與i的二進制的第j位比較，看是否為1，是則選中 47 bits++;//計算i中1的個數(shù)，也就是質(zhì)因數(shù)的個數(shù) 48 mult *= p[j]; 49 } 50 int cur = r / mult; 51 if (bits & 1)//若1的個數(shù)是奇數(shù)則進行加法，否則進行減法 52 sum += cur; 53 else sum -= cur; 54 } 55 return r - sum;//用總的數(shù)目-與n不互素的個數(shù) 56 } 57 int main(){ 58 init(); 59 int n,r; 60 while(cin>>n>>r){ 61 factor(n); 62 cout<<solve(r)<<endl; 63 } 64 return 0; 65 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/xin-hua/p/3213050.html

總結(jié)

以上是生活随笔為你收集整理的容斥原理的二进制实现模版的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。