Discussion @ 1375. Bill Clevers @ Timus Online Judge

Is there a faster solution than O(N)?(-)

Posted by SPIRiT 13 Aug 2007 19:32

Re: Is there a faster solution than O(N)?(-)

Posted by Denis Koshman 5 Aug 2008 01:40

Probably yes because O(N) solution doesn't use primality of 'p'.

Re: Is there a faster solution than O(N)?(-)

Posted by Cat36 31 Oct 2008 20:56

Yes.
If you can sols the equation x*x = c (mod p) faster then O(P)

Re: Is there a faster solution than O(N)?(-)

Posted by Cat36 31 Oct 2008 21:01

Denis Koshman wrote 5 August 2008 01:40

Probably yes because O(N) solution doesn't use primality of 'p'.

My O(N) solution uses primality of 'p'.

Discussion of Problem 1375. Bill Clevers