📜 WAYPOINT LESSON
Inclusion-Exclusion
⭐⭐⭐ advanced⏳ 30 min read📍 Lesson 174 of 281
Counting the union starts with the sum of singles, then subtracts pairs, adds triples: the LCM ladder with alternating signs.
Union counts without double counting
|A∪B∪C| = |A|+|B|+|C| - |A∩B|-|A∩C|-|B∩C| + |A∩B∩C|. For divisibility, intersections are LCMs. k up to 15-20 means bitmask enumeration of the 2^k subsets; signs alternate with subset size. Overflow discipline: LCMs explode — cap at N and bail.