Discussion @ 2102. Michael and Cryptography @ Timus Online Judge

Keworker `~ AC with Pollard's rho algorithm [2] // Problem 2102. Michael and Cryptography 14 Jul 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 [1] // Problem 2102. Michael and Cryptography 15 Jul 2024 08:30

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

Keworker `~ Re: AC with Pollard's rho algorithm // Problem 2102. Michael and Cryptography 18 Jul 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))

Discussion of Problem 2102. Michael and Cryptography