search

kth-competitive-programming / kactl

KTH Algorithm Competition Template Library (... eller KTHs AC-tillverkande lapp)
2.68k stars 711 forks source link

Factor.h can be hacked #253

Closed tatyam-prime closed 5 months ago

tatyam-prime commented 5 months ago

Factor.h currently uses a fixed RNG, f(x) = x * x + 1, which causes an infinite loop for n = 124376107291. Changing the RNG to f(x) = x * x + i may resolve this issue.

Reference: https://github.com/yosupo06/library-checker-problems/pull/918

lrvideckis commented 5 months ago

kactl should really add library checker tests

simonlindholm commented 5 months ago

Thank you for filing this! Apparently the cause was that our implementation of the Floyd cycle finding algorithm did not find the first element in the cycle, but one k*|cycle| steps from the starting point, and modulo both 352523 and 352817 there is just a single cycle of length 821 which then always gets found at the same time for both primes.

I agree with the suggested fix. It wasn't obvious to me that it would work for all n up to the limit of what modmul can handle, given that we now pass it values that are even further from [0,n), but it turns out to do for subtle reasons.

It would be super nice to run KACTL against the library checker test suite, agreed. I don't have the time to do it myself, unfortunately.

lrvideckis commented 5 months ago

oh nice, actually I have time to add them; (as I've already set them up for my own lib, so it should be pretty easy)