Discussion @ 1132. Square Root @ Timus Online Judge

Why I always got time exceeded?How to improve my program?I want to know the best algorithm.

Posted by Huang Yizheng 9 Nov 2001 16:17

Re: Why I always got time exceeded?How to improve my program?I want to know the best algorithm.

Posted by Algorist 10 Nov 2001 10:18

I think that there is a simple formula that is going to
work....

Does there any mathymatical formula exit?Or I have to improve my enumerating algorithm?

Posted by Huang Yizheng 12 Nov 2001 05:03

> I think that there is a simple formula that is going to
> work....

Re: Why I always got time exceeded?How to improve my program?I want to know the best algorithm.

Posted by XiangGuangTe 9 May 2004 14:45

I know the answer when (n mod 4)=3

The answer is +a^((n+1)/4), -a^((n+1)/4)

But I don't know the answer when (n mod 4)=1

Re: Why I always got time exceeded?How to improve my program?I want to know the best algorithm.

Posted by Gheorghe Stefan 10 May 2004 16:12

an efficient algorithm for this problem requires knowing very much of number theory: Legendre Symbols and other (i've found them on the web). You could search the web for quadratic residues modulo n...
if not found, I cand send you "my" source...

Discussion of Problem 1132. Square Root