The Inclusion-Exclusion Principle

Pillar: Set — "You're counting the union of sets by alternately adding and subtracting intersection sizes. The alternating signs correct for over-counting."

The Setup

How many integers in $[1, 100]$ are divisible by $2$ or $3$?

First instinct: count multiples of $2$ ($50$ of them) and multiples of $3$ ($33$ of them). Add them: $83$. But that's wrong — you've counted multiples of $6$ twice (once as multiples of $2$, once as multiples of $3$). There are $16$ multiples of $6$ in $[1, 100]$. Subtract them: $50 + 33 - 16 = 67$.

That correction — add individual counts, subtract double-counts — is inclusion-exclusion for two sets. When you have three, four, or twenty conditions, the same logic scales. The signs alternate: add singles, subtract pairs, add triples, subtract quadruples, and so on. Each layer corrects the over-counting introduced by the previous one.

This pattern appears everywhere in competitive programming: counting integers divisible by at least one prime, counting permutations avoiding certain positions, counting surjections. The principle is always the same — the only thing that changes is what the "sets" represent and how you compute their intersections.

Two Sets

Let $A$ and $B$ be finite sets. The size of their union is:

\[|A \cup B| = |A| + |B| - |A \cap B|\]

Think of it with a Venn diagram. When you add $|A|$ and $|B|$, every element in the overlap $A \cap B$ gets counted twice. Subtracting $|A \cap B|$ brings each element's count back to exactly one.

Concrete example. Let $A$ = multiples of $2$ in $[1, 30]$, $B$ = multiples of $5$ in $[1, 30]$.

$|A| = \lfloor 30/2 \rfloor = 15$
$|B| = \lfloor 30/5 \rfloor = 6$
$|A \cap B| = \lfloor 30/10 \rfloor = 3$ (multiples of $\text{lcm}(2, 5) = 10$)
$|A \cup B| = 15 + 6 - 3 = 18$

Check by listing: $\{2,4,5,6,8,10,12,14,15,16,18,20,22,24,25,26,28,30\}$ — exactly $18$ elements.

Three Sets

For three sets $A$, $B$, $C$:

\[|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|\]

Trace why the signs work. Start by adding all three individual sizes. Any element in exactly two sets gets counted twice — the pairwise subtractions fix that. But an element in all three sets gets counted $3$ times by the singles, subtracted $3$ times by the pairs, leaving it at $0$. The final $+|A \cap B \cap C|$ brings it back to $1$.

Track the count for an element in all three sets through each term:

Term	Running count
$+	A
$+	B
$+	C
$-	A \cap B
$-	A \cap C
$-	B \cap C
$+	A \cap B \cap C

Every element ends up counted exactly once, regardless of how many sets it belongs to. That's the invariant inclusion-exclusion maintains.

General Formula for $n$ Sets

The Inclusion-Exclusion Principle. For finite sets $A_1, A_2, \ldots, A_n$:

\[\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{k=1}^{n} (-1)^{k+1} \sum_{\substack{S \subseteq \{1,\ldots,n\} \\ |S| = k}} \left|\bigcap_{i \in S} A_i\right|\]

In words: iterate over all non-empty subsets $S$ of the index set $\{1, \ldots, n\}$. For each subset of size $k$, compute the intersection of those $k$ sets. Multiply by $(-1)^{k+1}$: positive for odd-sized subsets, negative for even-sized subsets. Sum everything.

Why does this work? For any element $x$ that belongs to exactly $m$ of the $n$ sets ($m \geq 1$), its contribution to the sum is:

\[\sum_{k=1}^{m} (-1)^{k+1} \binom{m}{k}\]

The element appears in $\binom{m}{k}$ intersections of size $k$ (choose which $k$ of its $m$ sets to intersect). Using the alternating sum identity from Ch5 L1:

\[\sum_{k=0}^{m} (-1)^k \binom{m}{k} = 0 \implies \sum_{k=1}^{m} (-1)^{k+1} \binom{m}{k} = 1\]

Every element in the union contributes exactly $1$. Every element outside all sets contributes $0$. The formula counts $|A_1 \cup \cdots \cup A_n|$ exactly.

Implementation: Bitmask Iteration

The formula says "iterate over all non-empty subsets." With $k$ conditions, there are $2^k - 1$ non-empty subsets. Represent each subset as a bitmask: an integer from $1$ to $2^k - 1$ where bit $i$ indicates whether condition $i$ is included.

For each bitmask:

Identify which conditions are in the subset (check each bit).
Compute the intersection size for that subset.
Count the number of set bits — that's the subset size $|S|$.
If $|S|$ is odd, add the intersection size. If even, subtract it.

long long inclusionExclusion(long long universeSize, vector<long long>& conditions) {
    int numConditions = conditions.size();
    long long unionSize = 0;
    for (int mask = 1; mask < (1 << numConditions); mask++) {
        long long intersectionSize = computeIntersection(universeSize, conditions, mask);
        int subsetSize = __builtin_popcount(mask);
        if (subsetSize % 2 == 1) unionSize += intersectionSize;
        else unionSize -= intersectionSize;
    }
    return unionSize;
}

The computeIntersection function depends on the problem. For divisibility problems, it's $\lfloor N / \text{product of selected values} \rfloor$. For forbidden positions in permutations, it's a different calculation. The bitmask skeleton stays the same.

Complexity

$O(2^k \times C)$ where $k$ is the number of conditions and $C$ is the cost of computing one intersection size. Since $2^k$ grows exponentially, this approach is practical only when $k$ is small — typically $k \leq 20$.

The Complement View

Often you don't want the size of the union. You want the count of elements in none of the sets. That's the complement:

\[|\text{none of } A_1, \ldots, A_k| = N - \left|\bigcup_{i=1}^{k} A_i\right|\]

where $N$ is the size of the universe. Many problems ask "how many integers in $[1, N]$ satisfy none of these conditions?" — compute the union with IE, then subtract from $N$.

This is the form you'll use in the CSES problem below and in the coprime counting lesson later in this chapter.

Worked Example: Divisibility in $[1, 100]$

Count integers in $[1, 100]$ divisible by $2$, $3$, or $5$.

Define three sets: $A_2$ = multiples of $2$, $A_3$ = multiples of $3$, $A_5$ = multiples of $5$.

Individual sizes (odd subsets, $+$):

$|A_2| = \lfloor 100/2 \rfloor = 50$
$|A_3| = \lfloor 100/3 \rfloor = 33$
$|A_5| = \lfloor 100/5 \rfloor = 20$

Pairwise intersections (even subsets, $-$):

$|A_2 \cap A_3| = |A_6| = \lfloor 100/6 \rfloor = 16$
$|A_2 \cap A_5| = |A_{10}| = \lfloor 100/10 \rfloor = 10$
$|A_3 \cap A_5| = |A_{15}| = \lfloor 100/15 \rfloor = 6$

Triple intersection (odd subset, $+$):

$|A_2 \cap A_3 \cap A_5| = |A_{30}| = \lfloor 100/30 \rfloor = 3$

Inclusion-exclusion:

\[|A_2 \cup A_3 \cup A_5| = (50 + 33 + 20) - (16 + 10 + 6) + 3 = 103 - 32 + 3 = 74\]

So $74$ integers in $[1, 100]$ are divisible by at least one of $2, 3, 5$, and $100 - 74 = 26$ integers are divisible by none of them (coprime to $30$).

Let's verify the bitmask approach produces the same result. With primes indexed as bit $0 = 2$, bit $1 = 3$, bit $2 = 5$:

Mask (binary)	Subset	Product	$\lfloor 100 / \text{product} \rfloor$	Sign	Contribution
$001$	$\{2\}$	$2$	$50$	$+$	$+50$
$010$	$\{3\}$	$3$	$33$	$+$	$+33$
$011$	$\{2,3\}$	$6$	$16$	$-$	$-16$
$100$	$\{5\}$	$5$	$20$	$+$	$+20$
$101$	$\{2,5\}$	$10$	$10$	$-$	$-10$
$110$	$\{3,5\}$	$15$	$6$	$-$	$-6$
$111$	$\{2,3,5\}$	$30$	$3$	$+$	$+3$

Total: $50 + 33 - 16 + 20 - 10 - 6 + 3 = 74$. Matches.

CSES Prime Multiples

Problem. Given $n$ and $k$ distinct primes $p_1, \ldots, p_k$ ($k \leq 20$), count integers in $[1, n]$ divisible by at least one $p_i$. Constraints: $n \leq 10^{18}$, $k \leq 20$.

This is textbook inclusion-exclusion. Define $A_i$ = multiples of $p_i$ in $[1, n]$. For any subset $S$ of the primes, the integers divisible by all primes in $S$ are the multiples of their product (since the primes are distinct, their LCM is their product):

\[\left|\bigcap_{i \in S} A_i\right| = \left\lfloor \frac{n}{\prod_{i \in S} p_i} \right\rfloor\]

Iterate over all $2^k - 1$ non-empty subsets via bitmask. For each subset, multiply the selected primes. If the product exceeds $n$, the floor division is $0$ — skip it. Otherwise, add or subtract $\lfloor n / \text{product} \rfloor$ depending on subset parity.

One trap: with $k = 20$ primes and $n$ up to $10^{18}$, the product of a large subset can overflow long long. Since the primes are at least $2$, any product exceeding $n$ contributes $0$. Check for overflow before multiplying: if product > upperBound / nextPrime, the multiplication would exceed upperBound, so skip.

The Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long upperBound;
    int numPrimes;
    cin >> upperBound >> numPrimes;
    vector<long long> primes(numPrimes);
    for (int i = 0; i < numPrimes; i++) cin >> primes[i];

    long long totalDivisible = 0;
    for (int mask = 1; mask < (1 << numPrimes); mask++) {
        long long product = 1;
        int subsetSize = 0;
        bool overflowed = false;
        for (int bit = 0; bit < numPrimes; bit++) {
            if (mask & (1 << bit)) {
                subsetSize++;
                if (product > upperBound / primes[bit]) {
                    overflowed = true;
                    break;
                }
                product *= primes[bit];
            }
        }
        if (overflowed) continue;
        long long contribution = upperBound / product;
        if (subsetSize % 2 == 1) totalDivisible += contribution;
        else totalDivisible -= contribution;
    }
    cout << totalDivisible << "\n";
    return 0;
}

$O(2^k \times k)$ time, $O(k)$ space. With $k \leq 20$, that's about $20$ million operations — runs in well under a second.

Common Mistakes

Overflow on the product. With $k = 20$ primes, even small primes produce products that overflow long long. Always check product > upperBound / nextPrime before multiplying. If this check is true, the product exceeds $n$ and the contribution is $0$ — skip the subset entirely.
Forgetting that the primes must be distinct for LCM = product. If the conditions aren't coprime, the intersection of $A_i$ and $A_j$ isn't multiples of $p_i \cdot p_j$ — it's multiples of $\text{lcm}(p_i, p_j)$. The CSES problem guarantees distinct primes, but other problems may not.
Starting the bitmask at $0$ instead of $1$. Mask $0$ is the empty subset, which contributes nothing. If you accidentally include it, you'll add $\lfloor n / 1 \rfloor = n$ to the total and get a wrong answer.

Quick Recap

Inclusion-exclusion counts $|A_1 \cup \cdots \cup A_k|$ by summing over all non-empty subsets of conditions, alternating signs: positive for odd-sized subsets, negative for even-sized.
Each element in exactly $m$ sets contributes exactly $1$ to the final sum, thanks to the alternating sum identity $\sum_{k=1}^{m}(-1)^{k+1}\binom{m}{k} = 1$.
Implementation iterates over $2^k$ bitmasks. For each, compute the intersection size and apply the sign based on popcount parity.
The complement view ($N - |$union$|$) counts elements satisfying none of the conditions.
Watch for overflow when the product of selected values exceeds the universe size — skip those subsets.

Problems

Problem	Link	Difficulty	Focus
CSES — Prime Multiples	cses.fi/problemset/task/2185	Medium	Direct IE over distinct primes; overflow handling
LC 878 — Nth Magical Number	leetcode.com/problems/nth-magical-number	Medium	Binary search on answer + IE for two sets; $
LC 2652 — Sum Multiples	leetcode.com/problems/sum-multiples	Easy	IE with three fixed divisors $(3, 5, 7)$; arithmetic series sums instead of counts

Mask (binary)	Subset	Product	\(\lfloor 100 / \text{product} \rfloor\)	Sign	Contribution
\(001\)	\(\{2\}\)	\(2\)	\(50\)	\(+\)	\(+50\)
\(010\)	\(\{3\}\)	\(3\)	\(33\)	\(+\)	\(+33\)
\(011\)	\(\{2,3\}\)	\(6\)	\(16\)	\(-\)	\(-16\)
\(100\)	\(\{5\}\)	\(5\)	\(20\)	\(+\)	\(+20\)
\(101\)	\(\{2,5\}\)	\(10\)	\(10\)	\(-\)	\(-10\)
\(110\)	\(\{3,5\}\)	\(15\)	\(6\)	\(-\)	\(-6\)
\(111\)	\(\{2,3,5\}\)	\(30\)	\(3\)	\(+\)	\(+3\)