Гарні числа#80

Гарні числа (Розбір)

Головна ідея: факторизувати нічого не треба. Числа сягають 10^{18}, розкласти їх на множники неможливо. Але добуток може «зіпсуватися» рівно двома способами, і обидва перевіряються дешево.

Спосіб перший — спільний дільник. Якщо якісь два числа a_i та a_j мають спільний дільник g = \gcd(a_i, a_j) > 1, то ділить обидва, отже g^2 ділить добуток a_i \cdot a_j, а значить і весь добуток. Відповідь — саме , і шукати щось інше не треба. Пар усього \binom{100}{2} < 5000, кожен — миттєвий.

Спосіб другий — окреме число. Якщо жодна пара не має спільного дільника, числа попарно взаємно прості, і тоді добуток гарний тоді й лише тоді, коли гарне кожне число окремо. Залишилось навчитися перевіряти одне a \le 10^{18}.

Ділимо його на всі прості до 10^6 (решето Ератосфена дає їх заздалегідь). Якщо якесь просте входить у степені — відповідь знайдена. Нехай після цього лишилося : усі його прості дільники більші за 10^6. Але три таких простих дали б понад 10^{18}, тож можливі лише варіанти

m = 1, \qquad m = p, \qquad m = p^2, \qquad m = p\cdot q .

З них негарний лише p^2. Отже досить перевірити, чи є точним квадратом — і якщо так, вивести його корінь.

Обережно з коренем. sqrt на числах порядку 10^{18} помиляється на одиницю через похибку double. Беріть sqrtl, а результат обов'язково перевіряйте перебором кількох сусідніх значень: c^2 = m має справджуватися точно, у цілих числах.

Складність — \mathcal{O}(N^2 \log a + N \cdot \pi(10^6)), тобто миттєво. Усі обчислення — у беззнакових -бітних; добуток чисел ніколи не рахуємо явно, він не вміститься нікуди.