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

Yes,I know all this.My algorithm is O(sqrt(n)),but I got Time Limited exceeded.The program uses only 1.5 sec at my computer when K=1000 and the dataset is random.It will cost also O(sqrt(n)) to get p
Posted by Blue cat 19 Mar 2002 15:46
Use precalc. array of all primes <= sqrt(10^9), I think ur program'll be much faster
Posted by I have answers to all your questions :) 19 Mar 2002 15:57
>
You think I'm so fool.Of course,I know such trick.Maybe the timelimit is too strict.I'll try more
Posted by Blue cat 19 Mar 2002 15:59
> >
This problem has a solution fastre than O(sqrt(N))
Posted by Leonid Volkov 20 Mar 2002 11:41
It has a pure analitical solution with almost no cycles needed :-)
The test are specially made so to do not allow all the possible O(sqrt
(N)) solutions pass!