二进制枚举的方法在实际问题中应用还是非常方便的。下面继续体会这一方法的使用。
先看如下的问题。
给出一个数n(1<=n<=1018),求1到n中,有多少个数不是2、5、7、11的倍数?
问题分析
如果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值最大可达10的18次方,因此采用上面的简单一重循环求解,运行太耗时。为提高效率,我们可以这样来解决问题。
先求出求1到n中有多少个数(设为cnt个)是2、5、7或11的倍数。
以n=100为例说明。
2的倍数有 n/2=100/2=50 个,即{2,4,6,8,10,…,100} 共50个。
5的倍数有 n/5=100/5=20 个,即{ 5,10,15,…,100 } 共20个。
7的倍数有 n/7=100/7=14 个,即{ 7,14,21,…,98} 共14个。
11的倍数有 n/11=100/11=9 个,即{ 11,22,33,…,99 } 共9个。
若将上面的4个数相加 cnt=50+20+14+9=93,得出“1到20中有93个数是2、5、7或11的倍数。”这个结论,肯定是不对的。
从上面的列举就可以看出,2×5=10,10的倍数有{10,20,…,100}这10个数,它们均被计数了两次,因此应减去 n/(2*5)=100/10=10。
同理,2×7、2×11、5×7、5×11、7×11这些数的倍数均被计算了2次,也应减去。
即 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这个数,在计数cnt时,是2的倍数加1,是5的倍数加1,是7的倍数加1,是2×5的倍数减1,是2×7的倍数减1,是5×7的倍数减1。因此,在Cnt计数中,70这个数相当1次也没有计数。因此,应加上它。同理,2×5×11、2×7×11、5×7×11这些数的倍数个数也均应加上。
这样加上后,2×5×7×11=770这个数的倍数个数又被多加了,应减去。
最终,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 个数是2、5、7或11的倍数。有 100-69=31个数不是2、5、7或11的倍数。
而对2、5、7或11这4个数的各种组合,可以采用4位二进制数枚举。
例如,0001表示只选中2,子集为{ 2 };0010表示只选中5,子集为{ 5 };0011表示选中2和5,子集为{ 2,5 };…;1111表示4个元素全部选中,子集为{ 2,5,7,11}。
对每种组合情况,计算选中的数的乘积的倍数的个数,若选中数的个数为奇数,则加上倍数的个数;若选中数的个数为偶数,则减去倍数的个数。最后,得到的结果就是所求的答案。
采用二进制枚举和容斥原理相结合的方法,编写如下的程序。
#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=