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

what's the mathematical method?
Posted by Li, Yi 3 Nov 2001 16:46
No subject
Posted by iii 4 Nov 2001 17:55
I have solution which take 1.001 sec for work...
It's - retrieval =)...
But - i can't make it faster... =(...
sorry
Posted by iii 4 Nov 2001 19:36
>
sorry
Posted by iii 4 Nov 2001 19:38
I wrote program that work 1.001 sec, but i can't make it
faster.
It's retrieval (searching)
Re: sorry
Posted by Hider 4 Nov 2001 19:48
> I wrote program that work 1.001 sec, but i can't make it
> faster.
> It's retrieval (searching)
You program have not work just 1.001 sec. The test system
stopped your program when it had been runned more than 1
sec.
Re: sorry
Posted by iii 5 Nov 2001 18:23
Thanx - i didn't know it =)
Re:
Posted by svr 8 Dec 2008 10:44
Use Tonelli algo for root(a,p) with precalculations
for all primes in [1..33000] and you will be first as I.
I don't say about evedent: basic number algos as
pow(a,n,p),inv(a,p) must be effectively implemented.
Also: there is simple Tonelli pseudocodes without
algebraic proves.