← all categories

Inclusion Exclusion b16dc065

Bitmask inclusion-exclusion: count of integers in [1, x] divisible by at least one of a small list of divisors (e.g. count numbers not coprime to a set of primes). Only practical for a small k (~20) — O(2^k) per query.

Time: O(2^k) per query. tested

content/math/inclusion-exclusion.h

ll countDivisibleByAny(ll x, vector<ll> &bad) {
    int k = (int)bad.size();
    ll res = 0;
    for (int m = 1; m < (1 << k); m++) {
        int amt = __builtin_popcount(m);
        ll L = 1;
        for (int i = 0; i < k; i++)
            if (m & (1 << i)) L = L / __gcd(L, bad[i]) * bad[i];
        ll cnt = x / L;
        res += (amt % 2 == 1 ? cnt : -cnt);
    }
    return res;
}