Discussion @ 1375. Bill Clevers @ Timus Online Judge

Timus Online Judge

Online Judge	Problems	Authors	Online contests
About Online Judge Frequently asked questions Site news Webboard Links	Problem set Submit solution Judge status Guide	Register Update your info Authors ranklist	Current contest Scheduled contests Past contests Rules

Discussion of Problem 1375. Bill Clevers

Show all messages Hide all messages

Is there a faster solution than O(N)?(-) SPIRiT 13 Aug 2007 19:32

Re: Is there a faster solution than O(N)?(-) 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)?(-) 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'.

Re: Is there a faster solution than O(N)?(-) Cat36 31 Oct 2008 20:56

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