一个你绝对能看懂的二进制枚举（容斥原理）ACM-ICPC 2018 沈阳赛区网络预赛

今天在打网络icpc选拔赛的时候，遇到了这道题，跟大佬队友学习了一下二进制枚举，正文在下面~

题目如下

​

Hint
In the all integers from 11 to 44, 11 and 33 is relatively-prime with the integer 44. So the answer is a[1]+a[3]=14.
样例输入
4 4
样例输出
14
题目来源
ACM-ICPC 2018 沈阳赛区网络预赛

思路
首先我们从a[n]的函数表达式入手，我们可以推导得a[n] = n*(n+1),接下来套一个分解质因数的板子，存入一个数组，然后用二进制枚举来解决问题。

正文

所谓二进制枚举 就是一种暴力的方式，用0,1来代表一个数字存在或不存在。
例如 0101 可以理解为 第一个物品要了，第二个不要，第三个要了，第四个不要。
那么这个和容斥原理有什么关系呢？
我们都知道容斥原理的公式为：

可能很多刚刚接触的小伙伴不太了解，其实有很多的问题需要容斥来解决，我举一个例子：
如果求100以内的除了 2的倍数 和 3的倍数的数 有多少个，我们可以很容易知道 2的倍数的个数是100/2，而3的倍数是100/3，“答案“是100-50-33 = 17
这显然是不对的 以6为例 6既是2的倍数也是三的倍数，显然减重了。
相信很多人要说啦 啊~ 我暴力行不行 我每个数都判断一下

#include<iostream>
using namespace std;
int main(){
	int ans = 0;
	for(int i = 1;i<+100;i++){
		if(i%2==0 || i%3==0){
			ans++;
		}
	}
	cout<<ans<<endl;
}

当然可以，但是这个时间复杂度是0（n）的，当n为1e9左右的数据就会超时了
那我们应该怎么办呢？(╯‵□′)╯︵┻━┻
这里我先引入容斥原理的概念
我们回到刚才的那个问题，我们有没有办法解决减重的情况？
这里我们就要运用容斥原理解决这个问题了，
100-2的倍数-3的倍数+6的倍数
减重复的加回来就好了，这个6是二和三的最小公倍数
好了这个问题我们已经很好的解决了，但是我们真的解决问题了吗？
我们在举一个例子 ：
100以内的数 求 2 3 5 7 11 的倍数，我们还是用刚才方法，
2的倍数+3的倍数+5的倍数+7的倍数+11的倍数- 。。。。。。。
这个时候我们犯难了 要减的有 c（5，2）= 10项 还有加的C（5，3）项。。。。。。。。。。
太麻烦了，明明这么简单的一道题，怎么解决？
这里我们就要引入二进制枚举的概念了：
代码先奉上：

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
int Gcd(int a,int b){
    return b==0?a:Gcd(b,a%b);
}
int Lcm(int a,int b){
    return a*b/Gcd(a,b);
}
int a[] = {2,3,5,7,11};
int main(){
    int n;
    int lena = 5;
    while(~scanf("%d",&n)){
        int ans = 0;
        for(int i = 0;i<(1<<lena);i++){ 
///每个数都有2种状态 ，在或不在 在本题中带的意思是2，3，5，7，11的倍数或不是，
///一共有2^5种可能
            int tmp  = 0;
            int lcm=1;
            for(int j = 0;j<lena;j++){  ///查看每一位的情况
                if((1<<j)&i){
                    tmp++;         ///记录有几个1
                    lcm*=a[j];
                }
            }
            if(tmp%2==1) ans+=n/lcm; //1的个数是奇数则加 偶数则减
            else ans-=n/lcm;
        }
        cout<<ans+n<<endl;
    }
}

所以，我们可以使用二进制枚举来模拟这个过程。

AC代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
#include<vector>
#include<queue>
#include<cmath>
#include<string>
#include<map>
using namespace std;
#define LL long long
#define N 100005
const LL mod=1e9+7;
const int INF=0x3f3f3f3f;

int n,m;
LL prime[20];
int cnt;
LL ni6,ni2;
LL qpow(LL a,LL k){
    LL tmp=1;
    while(k){
        if(k&1)
            tmp=(tmp*a)%mod;
        a=(a*a)%mod;
        k>>=1;
    }
    return tmp;
}
void fenjie(int x){
    int xx=sqrt(x);
    cnt=0;
    if(x%2==0){
        prime[cnt++]=2;
        while(x%2==0) x/=2;
    }
    int tmp=3;
    while(x!=1 && tmp<=xx){
        if(x%tmp==0){
            prime[cnt++]=tmp;
            while(x%tmp==0) x/=tmp;
        }
        tmp+=2;
    }
    if(x!=1) prime[cnt++]=x;
}

LL SUM(LL k,LL n){
    LL ans=(((((((k*k)%mod*n)%mod*(n+1))%mod)*(2*n+1))%mod)*ni6)%mod+((((k*n)%mod)*(n+1)%mod)*ni2)%mod;
    return ans;
}
void solve(){
    LL ans=SUM(1,n);
    for(int i=0;i<(1LL<<cnt);i++){
        LL x=1;
        LL tmp=0;
        for(int j=0;j<cnt;j++){
            if((1<<j)&i){
                x*=prime[j];
                tmp++;
            }
        }
        if(tmp%2==1)ans=(ans-SUM(x,n/x))%mod;
        else ans=(ans+SUM(x,n/x)+mod)%mod;
    }
    ans=(ans-SUM(1,n)+mod)%mod;
    printf("%lld\n",(ans+mod)%mod);
}
int main()
{
    ni6=qpow(6,mod-2);
    ni2=qpow(2,mod-2);
    while(~scanf("%d%d",&n,&m)){
    fenjie(m);
    solve();
    }
    return 0;
}