二进制枚举的方法在实际问题中应用还是非常方便的。下面继续体会这一方法的使用。
先看如下的问题。
给出一个数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=