本文共 1167 字，大约阅读时间需要 3 分钟。

题意：给你两个数n，m，即让你从1~n-1个数里有多少个能整除m个数中任意一个数？

题解：容斥原理：ORZ vici大牛写的比较详细   

/************************************************************                       容斥原理**   求几个数的组合（用二进制优化枚举各个状态）的最小公倍数，*   用n/lcm,如果这几个数的个数为奇数则加，偶数则减，*   注：当这几个数有0时，先把0给去掉***************************************************************/#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;typedef long long LL;int st[15];LL n;LL Gcd(LL a,LL b){//最大公约数    return b == 0 ? a : Gcd(b,a%b);}LL Lcm(LL a,LL b){//最小公倍数    return a * b / Gcd(a,b);}LL find(int num){//寻找组合    int cnt = 0,c = 0;    LL lcm = 1;    while(num){        if(num & 1) {lcm = Lcm(lcm,(LL)st[cnt]);c++;}        cnt ++;        num /= 2;    }    LL ans = (n-1) / lcm;    if(c % 2) return ans;    return -ans;}void solve(int m){//枚举各个状态二进制优化    LL sum = 0;    for(int i = 1;i < (1 << m) ;i++)    {        sum += find(i);    }    cout << sum << endl;}int main(){//    freopen("1.txt","r",stdin);    int x,m;    while(cin >> n >> m){        int k = 0;        for(int i = 0;i < m;i++){            cin >> x;            if(x) //如果存在0，先排除                st[k ++] = x;        }        solve(k);    }}
      
     
    
   

转载地址：http://tcsgi.baihongyu.com/