HDU 1796 How many integers can you find：容斥原理計數

問題

給定 N（< 2³¹）和 m（≤ 10）個不同正整數。求 N 以內（不含 N）能被至少一個給定數整除的整數個數。

容斥原理

對 m 個數的所有非空子集，計算其 LCM，若子集大小為奇數則加 N/LCM，偶數則減。
注意：N 本身若能整除則不計入，故 ans = Σ (−1)^|S|+1 ⌊(N−1)/LCM⌋。

代碼實現

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a,b) * b; }
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    ll N; int m;
    while (cin >> N >> m) {
        vector a;
        for (int i = 0; i < m; ++i) { ll x; cin >> x; if (x) a.push_back(x); }
        m = a.size(); ll ans = 0;
        for (int mask = 1; mask < (1<>i & 1) {
                cur = lcm(cur, a[i]);
                if (cur > N || cur <= 0) { overflow = true; break; }
                ++bits;
            }
            if (overflow) continue;
            ll cnt = (N - 1) / cur;
            ans += (bits & 1) ? cnt : -cnt;
        }
        cout << ans << '\n';
    }
    return 0;
}

複雜度

O(2^m × m)，m ≤ 10 時 10240 次操作，極快。