Розберемося, що насправді означає умова i = HCD(i, j).
Найбільший спільний дільник та дорівнює тоді й лише тоді, коли є дільником . Справді, HCD(i,j) завжди ділить , тому рівність можлива лише коли i \mid j; і навпаки, якщо i \mid j, то спільний дільник — найбільший можливий.
Отже, задача переформульовується так: скільки є пар з відрізка , у яких ділить ?
Зафіксуємо . Кратних до чисел у відрізку рівно — це i, 2i, 3i, \ldots Тому відповідь дорівнює
Ця сума рахується одним циклом за , чого при n \le 10^6 цілком достатньо.
Обов'язково використовуйте 64-бітний тип: сума приблизно дорівнює , що при n = 10^6 становить близько 1.4 \cdot 10^7 — тут ще безпечно, але звичка рахувати такі суми в long long рятує в схожих задачах.
Перевіримо на другому прикладі з умови (n = 4): 4 + 2 + 1 + 1 = 8 — саме стільки пар і перелічено.