These are the notes for Competitive Programming episode 24 (combinatorics 2). A housing society orders Diwali light strings for every flat divisible by 2 or 3, adds 15 + 10, and finds five strings left over: flats 6, 12, 18, 24 and 30 were counted twice. Fixing that one mistake is the inclusion-exclusion principle. We grow it from two groups to three to any number, list every group with a bitmask, meet an original problem, Festival Lights, where checking every flat up to 10^18 gets Time Limit Exceeded, and catch a sneaky bug with a stress test: multiplying the numbers instead of taking their lcm. Then we cap the lcm at n + 1 so it can never overflow, and solve a second original problem, Coprime Tokens, by counting the complement. Three real bugs close the episode. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hooks
Diwali lights. Flats 1 to 30. A flat gets a light string if its number is divisible by 2 or by 3. The treasurer counts 15 even flats and 10 multiples of 3 and orders 25 strings. Only 20 flats light up: every multiple of 6 was in both lists and was counted twice.
Cricket and football. In a class of 30, 18 students like cricket, 12 like football and 5 like both. 18 + 12 = 30 counts the 5 fans of both twice, so 25 like at least one, and 30 − 25 = 5 like neither.
Two buses. Bus A comes every 4 minutes, bus B every 6. They arrive together at 12, 24, 36 …: every 12 minutes, not every 24. 12 is the least common multiple of 4 and 6.
Attendance. A teacher who wants the number of students present often counts the absent ones and subtracts from the class size. Counting the opposite group and subtracting is the complement trick.
Two groups: add, then subtract the overlap
Write |A| for how many things are in group A.
- Union A ∪ B: everything in A or B (or both).
- Intersection A ∩ B: everything in both A and B.
- A Venn diagram draws each group as a circle; the overlap of the circles is the intersection.
Adding |A| + |B| counts everything in the overlap twice, so subtract it once:
|A ∪ B| = |A| + |B| − |A ∩ B|
Flats up to 30, divisible by 2 or 3: 15 + 10 − 5 = 20 (the overlap is the multiples of 6).
Three groups: add, subtract, add back
|A ∪ B ∪ C| = |A| + |B| + |C|
− |A ∩ B| − |A ∩ C| − |B ∩ C|
+ |A ∩ B ∩ C|
Why the last term? A number in all three groups (like 30 for 2, 3 and 5) is added 3 times by the singles and subtracted 3 times by the pairs, so it would end up not counted at all. Adding the triple overlap back counts it exactly once.
Numbers up to 100 divisible by 2, 3 or 5: 50 + 33 + 20 − 16 − 10 − 6 + 3 = 74.
The general rule: inclusion-exclusion
For k groups, go over every non-empty subset of the groups (a subset is any selection of them). For each subset, count the things in all of its groups. If the subset has an odd number of groups, add that count; if even, subtract it.
|A1 ∪ … ∪ Ak| = Σ over non-empty subsets S of (−1)^(|S|+1) · |intersection of the groups in S|
Include, exclude, include again: hence the name. Why it is right: a thing that belongs to exactly t ≥ 1 of the groups appears in C(t,1) subsets of size 1, C(t,2) of size 2, and so on, so it is counted C(t,1) − C(t,2) + C(t,3) − … = 1 time (this alternating sum of binomial coefficients, from episode 23, is always 1). A thing in no group is never counted.
Problem L · Festival Lights
Problem L · Festival Lights (written for this course). A society has flats numbered 1 … n. The committee chooses k numbers a1 … ak. A flat is lit if its number is divisible by at least one ai. Print the number of lit flats.
Input:
n kon the first line, thena1 … ak.1 ≤ n ≤ 10^18,1 ≤ k ≤ 18,1 ≤ ai ≤ 10^18, time limit 2 seconds.
| Sample input | Sample output | Why |
|---|---|---|
30 2 / 2 3 |
20 |
15 + 10 − 5 |
100 3 / 2 3 5 |
74 |
50 + 33 + 20 − 16 − 10 − 6 + 3 |
100 2 / 4 6 |
33 |
25 + 16 − 8 (multiples of 12) |
10 1 / 20 |
0 |
no flat ≤ 10 is divisible by 20 |
Brute force: check every flat (Time Limit Exceeded)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll n; int k;
cin >> n >> k;
vector<ll> a(k);
for (ll &x : a) cin >> x;
ll cnt = 0;
for (ll x = 1; x <= n; x++)
for (ll d : a)
if (x % d == 0) { cnt++; break; }
cout << cnt << "\n";
return 0;
}
| Input | Output |
|---|---|
30 2 / 2 3 |
20 |
100 2 / 4 6 |
33 |
1000000000000000000 18 / the first 18 primes 2 3 5 … 61 |
Time Limit Exceeded |
Why: 10^18 flats. Even at 10^9 checks a second that is over 31 years, before multiplying by k.
Every subset with a bitmask
Inclusion-exclusion never looks at a single flat. It needs one number per subset: how many flats ≤ n are divisible by every number in the subset. With k numbers there are 2^k − 1 non-empty subsets, and (episode 17) the integers m = 1 … 2^k − 1 list them all: bit i of m is 1 means ai is in the subset. The number of 1 bits is the popcount (__builtin_popcount(m)), and its parity gives the sign.
| mask | subset | flats ≤ 100 divisible by all | term |
|---|---|---|---|
| 001 | {2} | 50 | +50 |
| 010 | {3} | 33 | +33 |
| 011 | {2, 3} | 16 | −16 |
| 100 | {5} | 20 | +20 |
| 101 | {2, 5} | 10 | −10 |
| 110 | {3, 5} | 6 | −6 |
| 111 | {2, 3, 5} | 3 | +3 |
| total | 74 |
For k = 18 that is only 262143 subsets.
First attempt: multiply the numbers
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll n; int k;
cin >> n >> k;
vector<ll> a(k);
for (ll &x : a) cin >> x;
ll ans = 0;
for (int m = 1; m < (1 << k); m++) {
ll l = 1;
for (int i = 0; i < k; i++)
if (m >> i & 1) l = l * a[i];
int bits = __builtin_popcount(m);
ans += (bits % 2 ? 1 : -1) * (n / l);
}
cout << ans << "\n";
return 0;
}
Real outputs: 30 2 / 2 3 → 20 and 100 3 / 2 3 5 → 74. Both samples pass. But 100 2 / 4 6 → 37 (expected 33). The samples with prime numbers hide the bug.
A stress test catches the bug
Episode 5's recipe: a slow but obviously correct brute force, the fast solution, and many random tiny tests; print the first one where they disagree.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll brute(ll n, vector<ll>& a) {
ll c = 0;
for (ll x = 1; x <= n; x++)
for (ll d : a)
if (x % d == 0) { c++; break; }
return c;
}
ll fast(ll n, vector<ll>& a) { // product version
ll ans = 0;
for (int m = 1; m < (1 << a.size()); m++) {
ll l = 1;
for (int i = 0; i < (int)a.size(); i++)
if (m >> i & 1) l = l * a[i];
int s = __builtin_popcount(m) % 2 ? 1 : -1;
ans += s * (n / l);
}
return ans;
}
int main() {
mt19937 rng(10);
for (int t = 1; t <= 1000; t++) {
ll n = rng() % 30 + 1;
vector<ll> a(rng() % 3 + 1);
for (ll &x : a) x = rng() % 6 + 1;
ll b = brute(n, a), f = fast(n, a);
if (b != f) {
cout << "n=" << n << " a=";
for (ll x : a) cout << x << " ";
cout << "brute=" << b << " fast=" << f;
return 0;
}
}
cout << "all 1000 tests passed";
}
Real output:
n=18 a=2 4 brute=9 fast=11
By hand: up to 18 there are 9 even flats, and every multiple of 4 is already even, so the answer is 9. The overlap "divisible by both 2 and 4" is the 4 multiples of 4. The product version subtracted the multiples of 8 instead (only 2 of them): 9 + 4 − 2 = 11.
The fix: the lcm
The numbers divisible by both a and b are exactly the multiples of the least common multiple lcm(a, b): the smallest positive number both divide. Two buses every 4 and 6 minutes meet every 12. Multiplying is only right when a and b share no factor (they are coprime).
From episode 19's GCD:
lcm(a, b) = a / gcd(a, b) * b // divide first so the middle value stays small
lcm(4, 6) = 4 / 2 * 6 = 12
For a subset, fold it in one number at a time: l = lcm(l, ai). Changing one line of the stress test to l = lcm(l, a[i]); gives the real output all 1000 tests passed.
Overflow: cap the lcm at n + 1
With ai up to 10^18 the lcm can be far bigger than a long long can hold (about 9.2·10^18): it overflows. But notice: if l > n, no flat number is divisible by l, so n / l = 0 and the exact value of l doesn't matter. So compute each step in __int128 (a 128-bit integer type of g++, holding up to about 1.7·10^38) and store n + 1 whenever the result is above n. Every later step keeps it above n, and n / (n + 1) = 0.
The accepted solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll n; int k;
cin >> n >> k;
vector<ll> a(k);
for (ll &x : a) cin >> x;
ll ans = 0;
for (int m = 1; m < (1 << k); m++) {
ll l = 1;
for (int i = 0; i < k; i++) {
if (!(m >> i & 1)) continue;
__int128 t = (__int128)(l / gcd(l, a[i])) * a[i];
l = t > n ? n + 1 : (ll)t; // cap at n + 1
}
int bits = __builtin_popcount(m);
ans += (bits % 2 ? 1 : -1) * (n / l);
}
cout << ans << "\n";
return 0;
}
| Input | Output |
|---|---|
30 2 / 2 3 |
20 |
100 3 / 2 3 5 |
74 |
100 2 / 4 6 |
33 (the product version: 37) |
10 1 / 20 |
0 |
1000000000000000000 18 / 2 3 5 … 61 |
868412648149729878 in about 0.1 s |
1000000000000000000 2 / 4294967297 4294967295 |
465661286 |
The last answer was cross-checked with Python's exact big integers.
Problem L2 · Coprime Tokens (the complement)
Problem L2 · Coprime Tokens (written for this course). A canteen gives out tokens 1 … n. Token x wins a free chai if gcd(x, M) = 1 (x and M are coprime: they share no factor except 1). Print the number of winning tokens.
Input:
n M.1 ≤ n ≤ 10^18,1 ≤ M ≤ 10^12.
Sample: 30 12 → 10 (1 5 7 11 13 17 19 23 25 29).
Counting winners directly is awkward, so count the complement: winners = n − losers. A token loses if it shares a prime factor with M, i.e. it is divisible by at least one prime factor of M: that is Problem L with the ai being M's distinct primes. Find them with episode 20's trial division up to √M ≤ 10^6. M ≤ 10^12 has at most 11 different primes (2 · 3 · 5 · … · 31 = 200560490130 ≤ 10^12, and multiplying by 37 passes 10^12). Distinct primes are pairwise coprime, so the lcm of a subset is simply the product; the line l = l > n / p[i] ? n + 1 : l * p[i] caps it without overflow, because it checks l * p[i] > n as l > n / p[i] before multiplying.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll n, M;
cin >> n >> M;
vector<ll> p; // distinct primes of M
for (ll d = 2; d * d <= M; d++)
if (M % d == 0) {
p.push_back(d);
while (M % d == 0) M /= d;
}
if (M > 1) p.push_back(M);
int k = p.size();
ll bad = 0;
for (int m = 1; m < (1 << k); m++) {
ll l = 1;
for (int i = 0; i < k; i++)
if (m >> i & 1) l = l > n / p[i] ? n + 1 : l * p[i];
bad += (__builtin_popcount(m) % 2 ? 1 : -1) * (n / l);
}
cout << n - bad << "\n";
return 0;
}
| Input | Output |
|---|---|
30 12 |
10 |
100 30 |
26 |
10 1 |
10 (no primes: everyone wins) |
1000000000000000000 200560490130 |
152852151388986039 |
Counting numbers coprime to M is exactly what Euler's totient function does when n = M (episode 27).
Complexity vs the constraints
| Approach | Time | Worst case here | Verdict |
|---|---|---|---|
| Check every flat | O(n · k) | 10^18 · 18 | TLE |
| Inclusion-exclusion over subsets | O(2^k · k · log) (a gcd per step) | 2^18 · 18 ≈ 4.7·10^6 | ≈ 0.1 s |
| Problem L2: trial division + subsets | O(√M + 2^11 · 11) | ≈ 10^6 | instant |
Memory: O(k). The running time does not depend on n at all.
The rule: when n is huge but the number of conditions k is small (k ≤ about 20), count over the 2^k subsets of conditions, not over the items.
Common mistakes (and the real outputs)
Bug 1: no cap on the lcm
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll n; int k;
cin >> n >> k;
vector<ll> a(k);
for (ll &x : a) cin >> x;
ll ans = 0;
for (int m = 1; m < (1 << k); m++) {
ll l = 1;
for (int i = 0; i < k; i++) {
if (!(m >> i & 1)) continue;
l = l / gcd(l, a[i]) * a[i]; // no cap
}
int bits = __builtin_popcount(m);
ans += (bits % 2 ? 1 : -1) * (n / l);
}
cout << ans << "\n";
return 0;
}
Input 1000000000000000000 2 / 4294967297 4294967295. Real output: 1000000000465661286: more lit flats than there are flats. The two numbers share no factor, so their lcm is their product 4294967297 · 4294967295 = 2^64 − 1 ≈ 1.8·10^19, which overflows long long and wraps to −1. Then n / l = −10^18, subtracted (even subset) adds 10^18. The right answer is 465661286. Fix: __int128 and the cap at n + 1.
Bug 2: always adding
ans += n / l; // always add
100 3 / 2 3 5 → 138 (expected 74): every overlap is counted again instead of removed.
Bug 3: starting the mask at 0
for (int m = 0; m < (1 << k); m++) {
100 3 / 2 3 5 → -26 (expected 74). Mask 0 is the empty subset: its lcm is 1 and its popcount 0 is even, so it subtracts all n = 100 flats. Start at m = 1.
Summary table
| Mistake | What you see | Why | Fix |
|---|---|---|---|
l = l * a[i]; |
37 instead of 33 (4 and 6) |
numbers sharing a factor meet at the lcm, not the product | l = lcm(l, a[i]) |
l = l / gcd(l, a[i]) * a[i]; with no cap |
1000000000465661286 (> n) |
the lcm overflows long long |
__int128, cap at n + 1 |
ans += n / l; |
138 instead of 74 |
no alternating sign | odd popcount +, even − |
for (int m = 0; …) |
-26 instead of 74 |
the empty subset subtracts n | start at m = 1 |
for (ll x = 1; x <= n; x++) |
Time Limit Exceeded | 10^18 flats | inclusion-exclusion over subsets |
Mini project
Write a reusable countDivisibleByAny(n, a) function (with the lcm cap) and a stress tester for it. Then use it to build: (1) a range version count(L, R) = f(R) − f(L − 1); (2) coprimeCount(n, M); (3) a table of how many numbers ≤ 10^6 are divisible by none of the first k primes, for k = 1 … 10. Check every function against a brute force for all n ≤ 1000.
Practice
These follow the video's homework.
-
Count the x in [L, R] divisible by at least one ai. Example: L = 10, R = 30, a = 2 3.
Answer
Answer = f(R) − f(L − 1), where f(n) is Problem L's count for 1 … n. f(30) = 20, f(9) = 6 (2 3 4 6 8 9), so the answer is <b>14</b> (checked by brute force). -
Count the x ≤ n divisible by none of k given primes. Example: n = 100, primes 2 3 5.
Answer
The complement: n − f(n) = 100 − 74 = <b>26</b> (checked by brute force). -
Count the x ≤ n coprime to both M1 and M2. Example: n = 100, M1 = 4, M2 = 15.
Answer
x is coprime to both exactly when it is coprime to M1 · M2, i.e. divisible by none of the distinct primes of M1 and M2 together (here 2, 3, 5). Answer <b>26</b> (checked by brute force). Merge the two prime lists and remove duplicates first. -
How many strings of length n over the letters a, b, c use all three letters?
Answer
Total 3^n, minus strings missing a letter. Missing a given letter: 2^n (3 choices of letter); missing two given letters: 1^n (3 choices); missing all three: 0. Inclusion-exclusion: 3^n − 3 · 2^n + 3. n = 3: 6, n = 4: 36, n = 5: 150 (all checked by listing every string). In general, onto counts use C(k, i) from episode 23: Σ (−1)^i C(k, i) (k − i)^n. -
Without code: how many x ≤ 1000 are divisible by 6, 10 or 15?
Answer
166 + 100 + 66 − 33 − 33 − 33 + 33 = <b>266</b>. Every pair and the triple have lcm 30 (1000 / 30 = 33). Multiplying (60, 90, 150, 900) would give a wrong answer. Checked by brute force.
Quick quiz
How many x ≤ 60 are divisible by 4 or 6? (60 / 4 = 15, 60 / 6 = 10, 60 / 12 = 5, 60 / 24 = 2.)
A) 25 · B) 20 · C) 23 · D) 15
Answer
B. 15 + 10 − 60 / lcm(4, 6) = 15 + 10 − 5 = 20 (checked by brute force). C, 23, is the product trap: it subtracts the multiples of 24. A forgets to subtract the overlap at all.
Interview questions
- State the inclusion-exclusion principle. The size of a union equals the sum over every non-empty subset of the groups of (−1)^(size+1) times the size of their intersection.
- Why is every element counted exactly once? An element in t ≥ 1 groups is counted C(t,1) − C(t,2) + … ± C(t,t) = 1 time.
- How do you enumerate all subsets of k items? Loop m from 1 to 2^k − 1; bit i of m says whether item i is in; the popcount gives the subset size.
- Why lcm and not product? Numbers divisible by both a and b are the multiples of lcm(a, b); the product is only right for coprime a and b.
- How do you avoid overflow when the lcm grows past 10^18? Any l > n contributes n / l = 0, so cap l at n + 1, checking with
__int128or with the division testl > n / bbefore multiplying. - When does inclusion-exclusion beat a direct loop? When n is huge and the number of conditions k is small: O(2^k · k) is independent of n.
- What is the complement trick? Count the opposite (e.g. numbers sharing a factor with M) and subtract from the total.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Double counting | Counting the same thing more than once by adding overlapping groups | flat 6 in "÷2" and "÷3" |
| Set / group | A collection of things | flats divisible by 2 |
| |A| | How many things are in A | |flats ≤ 30 divisible by 2| = 15 |
| Union (∪) | In A or B (or both) | lit flats |
| Intersection (∩) | In both A and B | multiples of 6 |
| Venn diagram | Overlapping circles showing groups and their overlaps | cricket and football fans |
| Inclusion-exclusion | Add odd-sized intersections, subtract even-sized ones | 50 + 33 + 20 − 16 − 10 − 6 + 3 |
| Subset | Any selection from a collection | {2, 5} from {2, 3, 5} |
| Empty subset | The selection of nothing; skipped here | mask 0 |
| Bitmask | An integer whose bits say which items are chosen | 011 = {2, 3} |
| Popcount | Number of 1 bits | __builtin_popcount(5) = 2 |
| Least common multiple (lcm) | Smallest positive number divisible by both | lcm(4, 6) = 12 |
| Coprime | Sharing no factor except 1; gcd = 1 | 8 and 15 |
| Complement | Everything not in a group: total minus the group | winners = n − losers |
| Stress test | Comparing a fast solution with a brute force on many random small tests | n=18 a=2 4 brute=9 fast=11 |
| Integer overflow | A value too big for its type wraps around | 2^64 − 1 → −1 |
__int128 |
g++'s 128-bit integer type, up to about 1.7·10^38 | holds 10^18 · 10^18 |
| Cap at n + 1 | Replacing any value above n with n + 1, since n / l = 0 for l > n | l = t > n ? n + 1 : (ll)t |
Summary
- Adding the sizes of overlapping groups counts the overlap more than once: |A ∪ B| = |A| + |B| − |A ∩ B|.
- For k groups: add every odd-sized intersection, subtract every even-sized one. List the 2^k − 1 subsets with bitmasks; the popcount gives the sign.
- "Divisible by every number in a subset" means "a multiple of their lcm", not of their product. A stress test found
n=18 a=2 4where the product version said 11 instead of 9. - Cap the lcm at n + 1 (with
__int128) so it never overflows: n / (n + 1) = 0. - Problem L: 10^18 flats, 18 numbers, answer
868412648149729878in about 0.1 s instead of TLE. Problem L2: count coprime numbers by subtracting the complement. - Real bugs: no cap (
1000000000465661286> n), always adding (138), the empty subset (-26).
Solutions in C++, Java and Python
Problem L · Festival Lights
C++: the accepted solution above.
Java (tested on all four samples, 868412648149729878 for the 18 primes and 465661286 for the overflow input). Java has no 128-bit integer, so the cap uses the division test q > n / a[i] instead of multiplying first.
import java.io.*;
import java.util.*;
public class Main {
static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long n = Long.parseLong(st.nextToken());
int k = Integer.parseInt(st.nextToken());
long[] a = new long[k];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < k; i++) a[i] = Long.parseLong(st.nextToken());
long ans = 0;
for (int m = 1; m < (1 << k); m++) {
long l = 1;
for (int i = 0; i < k; i++) {
if ((m >> i & 1) == 0) continue;
long q = l / gcd(l, a[i]);
// q * a[i] > n <=> q > n / a[i] (no overflow)
l = (q > n / a[i]) ? n + 1 : q * a[i];
}
int sign = Integer.bitCount(m) % 2 == 1 ? 1 : -1;
ans += sign * (n / l);
}
System.out.println(ans);
}
}
Python (same tests, all match; about 0.5 s for k = 18). Python integers never overflow, so no cap is needed, but breaking out once l > n saves work.
import sys
from math import gcd
def main():
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + k]))
ans = 0
for m in range(1, 1 << k):
l = 1
for i in range(k):
if m >> i & 1:
l = l // gcd(l, a[i]) * a[i]
if l > n: # Python ints never overflow, but stop early
break
sign = 1 if bin(m).count("1") % 2 else -1
ans += sign * (n // l)
print(ans)
main()
Problem L2 · Coprime Tokens
C++: the program above.
Java (tested: 30 12 → 10, 100 30 → 26, 10 1 → 10, 1000000000000000000 200560490130 → 152852151388986039):
import java.util.*;
public class Cop {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong(), M = sc.nextLong();
List<Long> p = new ArrayList<>();
for (long d = 2; d * d <= M; d++)
if (M % d == 0) {
p.add(d);
while (M % d == 0) M /= d;
}
if (M > 1) p.add(M);
int k = p.size();
long bad = 0;
for (int m = 1; m < (1 << k); m++) {
long l = 1;
for (int i = 0; i < k; i++)
if ((m >> i & 1) == 1) l = l > n / p.get(i) ? n + 1 : l * p.get(i);
bad += (Integer.bitCount(m) % 2 == 1 ? 1 : -1) * (n / l);
}
System.out.println(n - bad);
}
}
Python (same tests, all match):
import sys
def main():
n, M = map(int, sys.stdin.read().split())
p, d = [], 2
while d * d <= M:
if M % d == 0:
p.append(d)
while M % d == 0:
M //= d
d += 1
if M > 1:
p.append(M)
bad = 0
for m in range(1, 1 << len(p)):
l = 1
for i in range(len(p)):
if m >> i & 1:
l *= p[i]
sign = 1 if bin(m).count("1") % 2 else -1
bad += sign * (n // l)
print(n - bad)
main()