Обсуждение @ 2102. Миша и криптография @ Timus Online Judge

Keworker `~ AC with Pollard's rho algorithm [3] // Задача 2102. Миша и криптография 14 июл 2024 11:11

I pass this problem with Sieve of Eratosthenes, but i think solution with Pollard's rho algorithm is funnier, and wrote it too.

If you cant pass it with this algo just use all prime modules from 1'000'000'007 to 1'000'001'393.

👑TIMOFEY👑`~ Re: AC with Pollard's rho algorithm [2] // Задача 2102. Миша и криптография 15 июл 2024 08:30

Did you check small dividers? ro pollard works very poorly with them

Keworker `~ Re: AC with Pollard's rho algorithm [1] // Задача 2102. Миша и криптография 18 июл 2024 16:32

If TL let me check all with O(sqrt(n)), I do it. I invoke rho pollard only if can not pass test with O(sqrt(n))

Solver Re: AC with Pollard's rho algorithm // Задача 2102. Миша и криптография 20 июл 2026 12:02

Sieve up to 1e6 - WA54
Sieve up to 1.5e6 - WA59
Sieve up to 1e7 - AC
:)

Обсуждение задачи 2102. Миша и криптография