二進(jìn)制枚舉（二）
二進(jìn)制枚舉的方法在實際問題中應(yīng)用還是非常方便的。下面繼續(xù)體會這一方法的使用。
先看如下的問題。
給出一個數(shù)n（1<=n<=1018），求1到n中，有多少個數(shù)不是2、5、7、11的倍數(shù)？
問題分析
如果n的值較小，可以采用一個簡單的一重循環(huán)進(jìn)行處理即可。編寫如下的程序。
#include <stdio.h> int main() { int n; while (scanf("%d",&n)!=EOF) { int i,cnt=0; for (i=1;i<=n;i++) { if (i%2!=0 && i%5!=0 && i%7!=0 && i%11!=0) cnt++; } printf("%d\n",cnt); } return 0; }
但由于題目中給定n值最大可達(dá)10的18次方，因此采用上面的簡單一重循環(huán)求解，運(yùn)行太耗時。為提高效率，我們可以這樣來解決問題。
先求出求1到n中有多少個數(shù)（設(shè)為cnt個）是2、5、7或11的倍數(shù)。
以n=100為例說明。
2的倍數(shù)有 n/2=100/2=50 個，即{2，4，6，8，10，…，100} 共50個。
5的倍數(shù)有 n/5=100/5=20 個，即{ 5，10，15，…，100 } 共20個。
7的倍數(shù)有 n/7=100/7=14 個，即{ 7，14，21，…，98} 共14個。
11的倍數(shù)有 n/11=100/11=9 個，即{ 11，22，33，…，99 } 共9個。
若將上面的4個數(shù)相加 cnt=50+20+14+9=93，得出“1到20中有93個數(shù)是2、5、7或11的倍數(shù)。”這個結(jié)論，肯定是不對的。
從上面的列舉就可以看出，2×5=10，10的倍數(shù)有{10，20，…，100}這10個數(shù)，它們均被計數(shù)了兩次，因此應(yīng)減去 n/(2*5)=100/10=10。
同理，2×7、2×11、5×7、5×11、7×11這些數(shù)的倍數(shù)均被計算了2次，也應(yīng)減去。
即 cnt=(n/2+n/5+n/7+n/11) –(n/(2*5)+n/(2*7)+n/(2*11) +n/(5*7) +n/(5*11) +n/(7*11))
這樣處理后，仍然不對。例如，2×5×7=70這個數(shù)，在計數(shù)cnt時，是2的倍數(shù)加1，是5的倍數(shù)加1，是7的倍數(shù)加1，是2×5的倍數(shù)減1，是2×7的倍數(shù)減1，是5×7的倍數(shù)減1。因此，在Cnt計數(shù)中，70這個數(shù)相當(dāng)1次也沒有計數(shù)。因此，應(yīng)加上它。同理，2×5×11、2×7×11、5×7×11這些數(shù)的倍數(shù)個數(shù)也均應(yīng)加上。
這樣加上后，2×5×7×11=770這個數(shù)的倍數(shù)個數(shù)又被多加了，應(yīng)減去。
最終，cnt=(n/2+n/5+n/7+n/11)
–(n/(2*5)+n/(2*7)+n/(2*11) +n/(5*7) +n/(5*11) +n/(7*11))
+（n/(2*5*7)+ n/(2*5*11) + n/(2*7*11) + n/(5*7*11)）
-（ n/(2*5*7*11)）
這就是所謂的容斥原理，簡單說就是“奇加偶減”。
這樣，n=100時，計算cnt=（100/2+100/5+100/7+100/11）-（100/10+100/14+100/22+100/35+100/55+100/77）+（100/70+100/110+100/154+100/385）-（100/770）
=（50+20+14+9）-（10+7+4+2+1+1）+（1+0+0+0+0）-0 =69。
即1到100中有 69 個數(shù)是2、5、7或11的倍數(shù)。有 100-69=31個數(shù)不是2、5、7或11的倍數(shù)。
而對2、5、7或11這4個數(shù)的各種組合，可以采用4位二進(jìn)制數(shù)枚舉。
例如，0001表示只選中2，子集為{ 2 }；0010表示只選中5，子集為{ 5 }；0011表示選中2和5，子集為{ 2,5 }；…；1111表示4個元素全部選中，子集為{ 2,5,7,11}。
對每種組合情況，計算選中的數(shù)的乘積的倍數(shù)的個數(shù)，若選中數(shù)的個數(shù)為奇數(shù)，則加上倍數(shù)的個數(shù)；若選中數(shù)的個數(shù)為偶數(shù)，則減去倍數(shù)的個數(shù)。最后，得到的結(jié)果就是所求的答案。
采用二進(jìn)制枚舉和容斥原理相結(jié)合的方法，編寫如下的程序。
#include <stdio.h> int main() { int p[4]={2,5,7,11}; long long n; while (scanf("%lld",&n)!=EOF) { long long ans=0; int i,j; for (i=1;i<(1<<4);i++) { long long muti=1; int cnt=0; for (j=0;j<4;j++) { if (i&(1<<j)) { cnt++; muti*=p[j]; } } if(cnt&1) ans+=n/muti; // 容斥原理，奇加偶減 else ans-=n/muti; } printf("%lld\n",n-ans); } return 0; }
【例1】可以找到幾個數(shù)
問題描述
給出一個整數(shù)N和一個有M個整數(shù)的整數(shù)集，有多少個比N小的整數(shù)，它們可以被集合中的任一整數(shù)整除。例如，N=12，M整數(shù)集是{2,3}，所以有另一個集合{2,3,4,6,8,9,10}，該集合的所有整數(shù)都可以被2或3整除。因此，可知道結(jié)果為7，即有7個數(shù)。
輸入
輸入包括多組測試用例。對于每組測試用例，第一行包含兩個整數(shù)N和M。第二行包含M個整數(shù)，并且它們都彼此不同。0<N<2^31，0<M<=10，且M個整數(shù)為非負(fù)且不會超過20。
輸出
對于每組測試用例，用1行輸出答案。
輸入樣例
12 2
2 3
輸出樣例
7
（1）編程思路。
采用二進(jìn)制枚舉和容斥原理求解。但由于在M個整數(shù)中選取的若干個數(shù)不一定全部兩兩互質(zhì)，可能存在公約數(shù)，因此在計算時，需要計算它們的最小公倍數(shù)。
（2）源程序。
#include <stdio.h> int gcd(int a,int b) { return a%b==0?b:gcd(b,a%b); } int main() { int n,m; while (scanf("%d%d",&n,&m)!=EOF) { int i,j,h=0,a[21]; for (i=0;i<m;i++) { scanf("%d",&a[h]); if (a[h]) h++; // 過濾掉 0 } m=h; int ans=0; for (i=1; i<1<<m;i++) // 二進(jìn)制枚舉各數(shù)的組合情況 { int cnt=0; // 組合中選取的數(shù)的個數(shù)（也是對應(yīng)二進(jìn)制數(shù)中1的個數(shù)） int t=1; // 選取各數(shù)的最小公倍數(shù) for (j=0;j<m;j++) { if (i&(1<<j)) { cnt++; t=a[j]/gcd(a[j],t)*t; } } if (cnt%2) // 容斥原理（選1個的情況-選2個的組合+選3個的組合- ……） { ans+=(n-1)/t; } else { ans-=(n-1)/t; } } printf("%d\n",ans); } return 0; }
將上面的源程序提交給HDU題庫 HDU 1796 How many integers can you find（http://acm.hdu.edu.cn/showproblem.php?pid=1796），可以Accepted。
【例2】互質(zhì)的數(shù)
問題描述
給定一個整數(shù)N，計算在整數(shù)A和B之間（包括A和B），有多少個整數(shù)與整數(shù)N是互質(zhì)的。
如果兩個整數(shù)的最大公約數(shù)是1，則稱它們是互質(zhì)的。數(shù)字1與每個整數(shù)都是互質(zhì)的。
例如，N=2，A=1，B=10時，在[1,10]中有5個整數(shù)與2是互質(zhì)的，它們是{1,3,5,7,9}。
輸入
輸入的第一行包含T（0＜T＜＝100）測試用例的數(shù)量，接下來的T行中的每一行包含三個整數(shù)A、B、N，其中（1≤A≤B≤1015）和（1≤N≤109）。
輸出
對于每個測試用例，輸出A和B之間的整數(shù)數(shù)（包括A和B），這些整數(shù)與N是互質(zhì)的。
輸入樣例
2
1 10 2
3 15 5
輸出樣例
Case #1: 5
Case #2: 10
（1）編程思路。
先求出整數(shù)n的全部質(zhì)因子，并保存在數(shù)組factor中。之后問題就變成了，分別求1~A-1和1~B之間各有多少個整數(shù)不是數(shù)組factor中的任何一個數(shù)的倍數(shù)。采用上面的二進(jìn)制枚舉和容斥原理進(jìn)行求解。
（2）源程序。
#include <stdio.h> long long factor[31]; long long cnt; // 整數(shù) n 所含的全部質(zhì)因子的個數(shù) void getfac(long long x) // 求整數(shù)x中的全部質(zhì)因子，并保存到全局?jǐn)?shù)組factor中 { long long i; if (x%2==0) { factor[cnt++]=2; while (x%2==0) x/=2; } for (i=3;i*i<=x;i+=2) // 尋找奇數(shù)質(zhì)因子 { if(x%i==0) { factor[cnt++]=i; while (x%i==0) x/=i; } } if (x>1) factor[cnt++]=x; } long long calc(long long x) // 計算1~x之間不能被數(shù)組factor中任一質(zhì)因子整除的數(shù)的個數(shù) { long long sum=0; long long i,j; for (i=1;i<(1<<cnt);i++) // 二進(jìn)制枚舉，所有質(zhì)因子的組合情況 { long long num=0; // 從質(zhì)因子集合中選擇質(zhì)因子的個數(shù) long long ans=1; // ans為質(zhì)因子積； for (j=0;j<cnt;j++) // 枚舉質(zhì)因子下標(biāo) { if ((i>>j)&1) // 第j個質(zhì)因子被選取 { num++; ans*=factor[j]; } } if (num&1) sum+=x/ans; // 容斥原理，奇+偶-，1~x中為ans倍數(shù)的數(shù)的個數(shù)x/ans else sum-=x/ans; } return x-sum; } int main() { int t,iCase=0; scanf("%d",&t); while (t--) { long long a,b,n; scanf("%lld%lld%lld",&a,&b,&n); cnt=0; getfac(n); long long x,y; x=calc(a-1); y=calc(b); printf("Case #%d: %lld\n",++iCase,y-x); } return 0; }
將上面的源程序提交給HDU題庫 HDU 4135 Co-prime （http://acm.hdu.edu.cn/showproblem.php?pid=4135），可以Accepted。
在HDU題庫中，還有2道題目與例2類似，給出參考源程序如下。
HDU 1695 GCD （http://acm.hdu.edu.cn/showproblem.php?pid=1695）。
#include <stdio.h> #include <string.h> long long calc(long long n,long long m) // 求區(qū)間[1,m]內(nèi)與n互質(zhì)的數(shù)的個數(shù) { long long factor[31]; // 求出整數(shù)n中的全部質(zhì)因子保存在數(shù)組factor中 long long len=0; // n中質(zhì)因子的個數(shù) long long i,j; if (n%2==0) { factor[len++]=2; while (n%2==0) n/=2; } for (i=3;i*i<=n;i+=2) // 尋找奇數(shù)質(zhì)因子 { if(n%i==0) { factor[len++]=i; while (n%i==0) n/=i; } } if (n>1) factor[len++]=n; long long sum=0; for (i=1;i<(1<<len);i++) // 二進(jìn)制枚舉，所有質(zhì)因子的組合情況 { long long cnt=0; // 從質(zhì)因子集合中選擇質(zhì)因子的個數(shù) long long p=1; // p為質(zhì)因子積； for (j=0;j<len;j++) // 枚舉質(zhì)因子下標(biāo) { if ((i>>j)&1) // 第j個質(zhì)因子被選取 { cnt++; p*=factor[j]; } } if (cnt&1) sum+=m/p; //容斥原理，奇+偶-，1~m中為p倍數(shù)的數(shù)的個數(shù)m/p else sum-=m/p; } return m-sum; } int main() { int t,iCase=0; scanf("%d",&t); while (t--) { long long a,b,c,d,k; scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k); if(k==0) { printf("Case %d: 0\n",++iCase); continue; } b/=k; d/=k; if (b>d) { long long temp; temp=b; b=d; d=temp; } long long i,ans=0; for (i=1;i<=d;i++) { long long k; k=i<b?i:b; ans+=calc(i,k); // 求區(qū)間[1,k]內(nèi)與i互質(zhì)的個數(shù) } printf("Case %d: %lld\n",++iCase,ans); } return 0; }
HDU 2841 Visible Trees（http://acm.hdu.edu.cn/showproblem.php?pid=2841）。
// 如果gcd(x,y)=z,ｇz!=1，那么一定被(x/z,y/z)的點(diǎn)擋住 // 即兩個數(shù)字(x,y)如果互質(zhì)，則可以被看到；如果不互質(zhì)，則看不到. // 所以本題就是要找出所有的互質(zhì)二元組(x,y) // 因此問題的最后變成：給定一個數(shù)x，找出它和1到y(tǒng)里面有多少個數(shù)互質(zhì)。 #include <stdio.h> #include <string.h> long long calc(long long n,long long m) // 求區(qū)間[1,m]內(nèi)與n互質(zhì)的數(shù)的個數(shù) { long long factor[31]; // 求出整數(shù)n中的全部質(zhì)因子保存在數(shù)組factor中 long long len=0; // n中質(zhì)因子的個數(shù) long long i,j; if (n%2==0) { factor[len++]=2; while (n%2==0) n/=2; } for (i=3;i*i<=n;i+=2) // 尋找奇數(shù)質(zhì)因子 { if(n%i==0) { factor[len++]=i; while (n%i==0) n/=i; } } if (n>1) factor[len++]=n; long long sum=0; for (i=1;i<(1<<len);i++) // 二進(jìn)制枚舉，所有質(zhì)因子的組合情況 { long long cnt=0; // 從質(zhì)因子集合中選擇質(zhì)因子的個數(shù) long long p=1; // p為質(zhì)因子積； for (j=0;j<len;j++) // 枚舉質(zhì)因子下標(biāo) { if ((i>>j)&1) // 第j個質(zhì)因子被選取 { cnt++; p*=factor[j]; } } if (cnt&1) sum+=m/p; //容斥原理，奇+偶-，1~m中為p倍數(shù)的數(shù)的個數(shù)m/p else sum-=m/p; } return m-sum; } int main() { int t; scanf("%d",&t); while (t--) { long long m,n; scanf("%lld%lld",&m,&n); long long i,ans=0; for (i=1;i<=m;i++) { ans+=calc(i,n); } printf("%lld\n",ans); } return 0; }
浙公網(wǎng)安備 33010602011771號