二进制枚举及容斥

输入n（<10^9），m(<=15)  接下来输入m个数（皆下于100）

求从1到n中不是这m个数的倍数的数的个数。

 

#include <iostream>

using namespace std;typedef long long LL;

LL a[15];

LL gcd(LL a,LL b)                 //求a和b的最大公约数{    if(b) return gcd(b,a%b);    return a;}

LL lcm(LL a,LL b)                //求a和b的最小公倍数{    return a/gcd(a,b)*b;}

int main(){    LL n,ans,l;    int i,j,m,flag;    while(cin>>n>>m)    {        ans=0;        for(i=0;i<m;i++)        cin>>a[i];        for(i=1;i<(1<<m);i++)           //利用2进制枚举出m个数的2^m-1种组合情况（减的1为都不取，即约数1的情况）        {            l=1;flag=0;            for(j=0;j<m;j++)              //对i的2进制从第1位到第m位判读            {                if((1<<j)&i)                  //判断2进制i的第j位是否为1，即是否取了a[j]                {                    l=lcm(a[j],l);                    if(l>n) break;                    flag++;                }            }            if(flag&1) ans+=n/l;                      else       ans-=n/l;        }        cout<<n-ans<<endl;    }    return 0;}

转载于:https://www.cnblogs.com/chen9510/p/4699571.html