Тестування пам`яті#357

Тестування пам`яті (Editorial)

Треба порахувати, скільки чисел від до діляться на або на . Це класичне застосування формули включень-виключень.

Кратних до у відрізку рівно , кратних до — . Якщо просто додати ці дві величини, то числа, кратні обом одразу, буде враховано двічі, тому їх треба відняти один раз.

Число ділиться і на , і на тоді й лише тоді, коли воно ділиться на їхнє найменше спільне кратне

\mathrm{lcm}(A, B) = \frac{A \cdot B}{\gcd(A, B)}.

Отже, відповідь дорівнює

\left\lfloor \frac{N}{A} \right\rfloor + \left\lfloor \frac{N}{B} \right\rfloor - \left\lfloor \frac{N}{\mathrm{lcm}(A,B)} \right\rfloor.

Дуже поширена помилка — узяти замість НСК просто добуток A \cdot B. Це правильно лише коли і взаємно прості; наприклад, для A = 2, B = 4 добуток дав би замість правильного НСК .

Друга пастка — переповнення: обчислюйте НСК як A / \gcd(A,B) \cdot B (спочатку ділення, потім множення), щоб проміжний добуток не вискочив за межі типу.

Найбільший спільний дільник знаходиться алгоритмом Евкліда за .