Новий алгоритм шифрування#147

Новий алгоритм шифрування (Розбір)

Треба порахувати пари з 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, то

C(x) = \sum_{S \subseteq \{1..t\}} (-1)^{|S|} \left\lfloor \frac{x}{\prod_{i \in S} p_i} \right\rfloor.

Різних простих у числа до 3 \cdot 10^4 не більше шести, тому підмножин щонайбільше — це швидко.

Розклад самого теж робиться пробними діленнями за \mathcal{O}(\sqrt{P}); при бажанні можна заздалегідь побудувати решето з найменшим простим дільником і отримати розклад за \mathcal{O}(\log P).

Загальна складність — приблизно \mathcal{O}(\sqrt{K} \cdot 2^t). Відповідь може бути великою, тому накопичуйте її у 64-бітному типі.