guest@cp-base:~/home/combinatorics$
templates/inclusion-exclusion.cpp
compilable
$cat templates/inclusion-exclusion

Inclusion-Exclusion

Count elements satisfying none/any of n properties using bitmask inclusion-exclusion.

[Combinatorics]|
Jul 9, 2026
|explanatory_notes.md|
#inclusion-exclusion#coprime#bitmask#counting
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int coprimeCount(int n, int r) {
    vector<int> p;
    for (int i = 2; (ll)i * i <= n; i++) {
        if (n % i == 0) {
            p.push_back(i);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) p.push_back(n);

    int sum = 0;
    for (int msk = 1; msk < (1 << (int)p.size()); msk++) {
        int mult = 1, bits = __builtin_popcount(msk);
        for (int i = 0; i < (int)p.size(); i++)
            if (msk >> i & 1) mult *= p[i];
        if (bits & 1) sum += r / mult;
        else sum -= r / mult;
    }
    return r - sum;
}

int divisibleByAny(int n, vector<int>& a) {
    int m = a.size(), sum = 0;
    for (int msk = 1; msk < (1 << m); msk++) {
        ll lcm = 1;
        int bits = __builtin_popcount(msk);
        bool overflow = false;
        for (int i = 0; i < m; i++) {
            if (msk >> i & 1) {
                lcm = lcm / __gcd(lcm, (ll)a[i]) * a[i];
                if (lcm > n) { overflow = true; break; }
            }
        }
        if (overflow) continue;
        if (bits & 1) sum += n / lcm;
        else sum -= n / lcm;
    }
    return sum;
}
43 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)

Inclusion-Exclusion Principle

Corrects over-counting by alternately adding and subtracting intersections.

Formula

∣A1∪⋯∪An∣=∑∣Ai∣−∑∣Ai∩Aj∣+⋯+(−1)n+1∣A1∩⋯∩An∣|A_1 \cup \cdots \cup A_n| = \sum |A_i| - \sum |A_i \cap A_j| + \cdots + (-1)^{n+1} |A_1 \cap \cdots \cap A_n|

Bitmask Approach

Iterate all 2p2^p subsets. For each subset of size kk: add if kk is odd, subtract if even.

Functions

  • coprimeCount(n, r) — count integers in [1,r][1, r] coprime to nn

  • divisibleByAny(n, a) — count integers in [1,n][1, n] divisible by at least one element of aa (uses LCM for intersections)

    • When to Use

  • "How many from 11 to NN are NOT divisible by any of these?"

  • Coprime counting, derangements

  • Property set must be small (p≤20p \le 20) for 2p2^p enumeration

    • Complexity

  • Time — O(2p⋅p)O(2^p \cdot p)

  • Space — O(p)O(p)