题目描述

思路：
一个集合Sm代表能被质数m整除的元素的个数
最后答案是s1 ∪ s2 ∪…… Sm（运用容斥原理求解）
1.通过之前的分析，n /( p[i] * p[j] ……p[k] )表示一次满足条件的情况。
2.通过容斥原理的思想              
一共2^m - 1个情况，符号取决于一次选法里选了多少个集合。
因此应用位运算来枚举所有情况。
每一种情况的二进制表示

流程：
1.从1开始枚举到2^m - 1.
2.二进制从地位到高位枚举，如果对应位
j = 1， 代表至少包含了质数p[j] 。（特判，如果质数之积大于n，这种情况不存在n被整除）
3.把个数 n / t 加到答案里， 根据（集合中的个数cnt判断）

对容斥原理的分析

算法1

(容斥原理) $O(2^m * m)$

C++ 代码

#include<iostream>
using namespace std;
typedef long long LL;
const int N = 20;
int p[N];
int n, m;
int main()
{
    cin >> n >> m;
    for(int i = 0; i < m; ++i)cin >> p[i];
    /*答案*/
    int res = 0;
    /*1.从1开始枚举，枚举到2^m次方*/
    for(int i = 1; i < 1 << m; ++i)
    {
        /*判断一种情况中选了多少个集合*/
        /*t表示当前的乘积，cnt表示当前i中有几个1（当前选法中有几个集合）*/
         int t = 1, cnt = 0;
         /*不包含全都不选的情况*/
         for(int j = 0; j < m; ++j)
         {
             /*如果当前位是1的话，添加集合*/
             if(1 & i >> j) 
            {
                 cnt++;
                /*如果p[1] * p[2] *…… > n , 不用算，肯定不能整除了。*/
                if((LL) t * p[j] > n)
                {
                    t = -1;
                    break;
                }
                t *= p[j];
            }
         }
         /*把每种情况的整数加到答案里*/
        if(t != -1)
        {
            /*判断当前到第有几个集合，如果有奇数个集合，加上，偶数个减去*/
            //cout << cnt << endl;
            if(cnt % 2 == 0)
                res -= n / t;
            else
                res += n / t;
        }
    }
    cout << res << endl;
    return 0;
}