Треба порахувати пари з 1 < P < Q, взаємно прості, для яких P \cdot Q \le K.
Переберемо менший ключ . Оскільки P < Q, маємо P^2 < P \cdot Q \le K, тому достатньо перебирати від доки P^2 < K — це щонайбільше близько 3 \cdot 10^4 значень при K \le 10^9.
Для фіксованого число має задовольняти дві умови: P < Q \le \lfloor K/P \rfloor і \gcd(P, Q) = 1. Отже, треба порахувати кількість взаємно простих з чисел у відрізку (P,\; \lfloor K/P \rfloor].
Позначимо через кількість чисел від до , взаємно простих з . Тоді шукана величина дорівнює C(\lfloor K/P \rfloor) - C(P).
Функцію рахуємо включеннями-виключеннями за різними простими дільниками . Якщо це прості p_1, \ldots, p_t, то
Різних простих у числа до 3 \cdot 10^4 не більше шести, тому підмножин щонайбільше — це швидко.
Розклад самого теж робиться пробними діленнями за \mathcal{O}(\sqrt{P}); при бажанні можна заздалегідь побудувати решето з найменшим простим дільником і отримати розклад за \mathcal{O}(\log P).
Загальна складність — приблизно \mathcal{O}(\sqrt{K} \cdot 2^t). Відповідь може бути великою, тому накопичуйте її у 64-бітному типі.