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

为了解决这个问题，我们需要计算区间[1, n]中不被给定数组中的任何一个数整除的数的个数。我们可以通过反向思维，计算被至少一个数整除的数的个数，然后用总数减去这个数目来得到结果。

方法思路

解决代码

#include 
   
    using namespace std;int main() {    ios::sync_with_stdio(0);    long long n, m;    vector
    
      a;    for (int i = 0; i < m; ++i) {        int num;        cin >> num;        a.push_back(num);    }        // 去重    sort(a.begin(), a.end());    auto it = unique(a.begin(), a.end());    a.erase(it, a.end());    m = it - a.begin();        long long ans = n;    for (int mask = 1; mask < (1 << m); ++mask) {        int k = __builtin_popcount(mask);        long long lcm_val = 1;        bool overflow = false;        for (int j = 0; j < m; ++j) {            if (mask & (1 << j)) {                int num = a[j];                if (lcm_val == 0) {                    lcm_val = num;                } else {                    long long g = __gcd(lcm_val, num);                    lcm_val = (lcm_val / g) * num;                    if (lcm_val > n) {                        overflow = true;                        break;                    }                }            }        }        if (overflow) continue;        long long count = n / lcm_val;        if (k % 2 == 1) {            ans += count;        } else {            ans -= count;        }    }    cout << ans << endl;    return 0;}
    
   

代码解释

这种方法通过枚举所有子集并利用容斥原理，高效地解决了问题，确保了计算的准确性和效率。

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