solution

Theo nguyên lý bù trừ (inclusion–exclusion), với hai tập $A$ và $B$:

$|A \cup B| = |A| + |B| - |A \cap B|.$

Cho $n$, $a$, $b$. Hãy đếm số nguyên trong đoạn $[1, n]$ chia hết cho $a$ hoặc chia hết cho $b$.

Số chia hết cho $a$ là $\lfloor n/a \rfloor$; chia hết cho $b$ là $\lfloor n/b \rfloor$; chia hết cho cả hai (tức cho $\mathrm{lcm}(a,b)$) là $\lfloor n/\mathrm{lcm}(a,b) \rfloor$.

Ví dụ: $n=10, a=2, b=3$: bội của 2 là 5 số, bội của 3 là 3 số, bội của 6 là 1 số → $5+3-1=7$.