|
|
back to boardShow all messages Hide all messagesIf you know that 'n' is on period, you may find 'q' by checking n+1, n+2, n+3, ... till you hit identical to 'n' state. Then, when you know 'q', you may iterate from states '1' and '1+q' till they match, this way you'll find 'p'.
This relies on a guess that iteratively you won't get TL. I used value of 1'500'000, but I don't know if it has a proof or if it means weak tests. For A1>0 there is a proof as there are only ~1M distinct Xi, Xi+1 pairs whose product does not overflow 100'000. But as for A1=0 case - I don't know... Theoretically p or q can be as large as ~100'000^2. Is is possible not to set limitation on number of different pairs in solution.
I remembered last pair (x_s, x_{s+1}) where s is the biggest power of two less than current position. And I compared all pairs till the next power of two to this remembered pair. |
|
|
