Chapter 89

Home

Inclusion-Exclusion Principle

Count the union of sets by adding single sets, subtracting pairwise intersections, adding triple intersections, and so on. Combined with bitmask enumeration, it solves counting problems with multiple constraints.

The Formula

|A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|

For N sets, enumerate all 2^N - 1 non-empty subsets.
Add if subset size is odd, subtract if even.

C++ — count numbers divisible by any of K factors

long long count_divisible(vector& factors, long long N) {
    int k = factors.size();
    long long ans = 0;

    for (int mask = 1; mask < (1 << k); mask++) {
        long long lcm = 1;
        int bits = 0;
        for (int i = 0; i < k; i++) {
            if (mask & (1 << i)) {
                lcm = lcm * factors[i] / __gcd(lcm, (long long)factors[i]);
                bits++;
                if (lcm > N) break;  // overflow guard
            }
        }
        long long cnt = N / lcm;
        if (bits % 2) ans += cnt;   // odd → add
        else ans -= cnt;            // even → subtract
    }
    return ans;
}

// Counts |A₁ ∪ A₂ ∪ ... ∪ A_k| where A_i = numbers divisible by factor[i]

Key Takeaways