Степан і пари#11

Степан і пари (Розбір)

Розберемося, що насправді означає умова i = HCD(i, j).

Найбільший спільний дільник та дорівнює тоді й лише тоді, коли є дільником . Справді, HCD(i,j) завжди ділить , тому рівність можлива лише коли i \mid j; і навпаки, якщо i \mid j, то спільний дільник — найбільший можливий.

Отже, задача переформульовується так: скільки є пар з відрізка , у яких ділить ?

Зафіксуємо . Кратних до чисел у відрізку рівно — це i, 2i, 3i, \ldots Тому відповідь дорівнює

\sum_{i=1}^{n} \left\lfloor \frac{n}{i} \right\rfloor.

Ця сума рахується одним циклом за , чого при n \le 10^6 цілком достатньо.

Обов'язково використовуйте 64-бітний тип: сума приблизно дорівнює , що при n = 10^6 становить близько 1.4 \cdot 10^7 — тут ще безпечно, але звичка рахувати такі суми в long long рятує в схожих задачах.

Перевіримо на другому прикладі з умови (n = 4): 4 + 2 + 1 + 1 = 8 — саме стільки пар і перелічено.