二进制枚举的方法在实际问题中应用还是非常方便的。下面继续体会这一方法的使用。
先看如下的问题。
给出一个数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=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】可以找到几个数
问题描述
给出一个整数N和一个有M个整数的整数集，有多少个比N小的整数，它们可以被集合中的任一整数整除。例如，N=12，M整数集是{2,3}，所以有另一个集合{2,3,4,6,8,9,10}，该集合的所有整数都可以被2或3整除。因此，可知道结果为7，即有7个数。
输入
输入包括多组测试用例。对于每组测试用例，第一行包含两个整数N和M。第二行包含M个整数，并且它们都彼此不同。0<N<2^31，0<M<=10，且M个整数为非负且不会超过20。
输出
对于每组测试用例，用1行输出答案。
输入样例
12 2
2 3
输出样例
7
（1）编程思路。
采用二进制枚举和容斥原理求解。但由于在M个整数中选取的若干个数不一定全部两两互质，可能存在公约数，因此在计算时，需要计算它们的最小公倍数。
（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++) // 二进制枚举各数的组合情况
{
int cnt=0; // 组合中选取的数的个数（也是对应二进制数中1的个数）
int t=1; // 选取各数的最小公倍数
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】互质的数
问题描述
给定一个整数N，计算在整数A和B之间（包括A和B），有多少个整数与整数N是互质的。
如果两个整数的最大公约数是1，则称它们是互质的。数字1与每个整数都是互质的。
例如，N=2，A=1，B=10时，在[1,10]中有5个整数与2是互质的，它们是{1,3,5,7,9}。
输入
输入的第一行包含T（0＜T＜＝100）测试用例的数量，接下来的T行中的每一行包含三个整数A、B、N，其中（1≤A≤B≤1015）和（1≤N≤109）。
输出
对于每个测试用例，输出A和B之间的整数数（包括A和B），这些整数与N是互质的。
输入样例
2
1 10 2
3 15 5
输出样例
Case #1: 5
Case #2: 10
（1）编程思路。
先求出整数n的全部质因子，并保存在数组factor中。之后问题就变成了，分别求1~A-1和1~B之间各有多少个整数不是数组factor中的任何一个数的倍数。采用上面的二进制枚举和容斥原理进行求解。
（2）源程序。
#include <stdio.h>
long long factor[31];
long long cnt; // 整数 n 所含的全部质因子的个数
void getfac(long long x) // 求整数x中的全部质因子，并保存到全局数组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) // 寻找奇数质因子
{
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之间不能被数组factor中任一质因子整除的数的个数
{
long long sum=0;
long long i,j;
for (i=1;i<(1<<cnt);i++) // 二进制枚举，所有质因子的组合情况
{
long long num=0; // 从质因子集合中选择质因子的个数
long long ans=1; // ans为质因子积；
for (j=0;j<cnt;j++) // 枚举质因子下标
{
if ((i>>j)&1) // 第j个质因子被选取
{
num++;
ans*=factor[j];
}
}
if (num&1) sum+=x/ans; // 容斥原理，奇+偶-，1~x中为ans倍数的数的个数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) // 求区间[1,m]内与n互质的数的个数
{
long long factor[31]; // 求出整数n中的全部质因子保存在数组factor中
long long len=0; // n中质因子的个数
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) // 寻找奇数质因子
{
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++) // 二进制枚举，所有质因子的组合情况
{
long long cnt=0; // 从质因子集合中选择质因子的个数
long long p=1; // p为质因子积；
for (j=0;j<len;j++) // 枚举质因子下标
{
if ((i>>j)&1) // 第j个质因子被选取
{
cnt++;
p*=factor[j];
}
}
if (cnt&1) sum+=m/p; //容斥原理，奇+偶-，1~m中为p倍数的数的个数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); // 求区间[1,k]内与i互质的个数
}
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)的点挡住
// 即两个数字(x,y)如果互质，则可以被看到；如果不互质，则看不到.
// 所以本题就是要找出所有的互质二元组(x,y)
// 因此问题的最后变成：给定一个数x，找出它和1到y里面有多少个数互质。
#include <stdio.h>
#include <string.h>
long long calc(long long n,long long m) // 求区间[1,m]内与n互质的数的个数
{
long long factor[31]; // 求出整数n中的全部质因子保存在数组factor中
long long len=0; // n中质因子的个数
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) // 寻找奇数质因子
{
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++) // 二进制枚举，所有质因子的组合情况
{
long long cnt=0; // 从质因子集合中选择质因子的个数
long long p=1; // p为质因子积；
for (j=0;j<len;j++) // 枚举质因子下标
{
if ((i>>j)&1) // 第j个质因子被选取
{
cnt++;
p*=factor[j];
}
}
if (cnt&1) sum+=m/p; //容斥原理，奇+偶-，1~m中为p倍数的数的个数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;
}
参考源程序
标签：11,二进制,个数,long,int,枚举,factor,100
From： https://www.cnblogs.com/cs-whut/p/16926858.html