ENG  RUSTimus 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
back to board

Discussion of Problem 1132. Square Root

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...