python/TangDou/AcWing/RongChi/890.cpp

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define endl "\n"

int n, m;      // n:质数个数，m:1~m的数字中有多少个可以被质数序列中至少一个整数整除。
               // 注意：代码里的n,m与模板题目中的含义相反！一定要注意!!!!!!!!!!!!
vector<int> p; // 质数数组

signed main() {
    cin >> m >> n; // 与m互质,n个质数！

    // 读入n个质数,为了使用vector<int>，读入时确实不太方便
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        p.push_back(x);
    }

    // ① 枚举从1到 2^n-1,每个数字，代表一种状态，每个状态代表一种质数的挑选办法
    // 当然，这些整数值的乘积可能大于n,大于的没用，只要小于等于n的
    int s = 0;
    for (int i = 1; i < 1 << p.size(); i++) {
        int t = 1, cnt = 0; // 累乘积，质因子个数
        // ② 在对应的整数值确定后，枚举此数值的每一个数位
        for (int j = 0; j < p.size(); j++)
            if (i >> j & 1) {       // ③判断当前数位是不是1,是1表示当前数位选中
                if (t * p[j] > m) { // 乘积不能超过最大值m，控制在[1~m]范围内
                    t = 0;          // s=0代表本次挑选的组合失败，无效
                    break;          // 由于i是由小到大遍历的，前面的都无效了，后面的肯定更大，更无效，不用继续了
                }
                cnt++;     // 选择的质因子个数
                t *= p[j]; // 累乘积
            }
        if (t) {            // 超过范围的，s=0,所以，现在代表只讨论在范围内的
            if (cnt & 1)    // 质数因子数量，奇数加
                s += m / t; // 引理内容，代表m里面有多少个这个数字s的倍数
            else            // 偶数减
                s -= m / t;
        }
    }
    cout << s << endl;
}