Обсуждение @ 1204. Идемпотенты @ Timus Online Judge

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

Послано Blue cat 19 мар 2002 15:46

Use precalc. array of all primes <= sqrt(10^9), I think ur program'll be much faster

Послано I have answers to all your questions :) 19 мар 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

Послано Blue cat 19 мар 2002 15:59

> >

This problem has a solution fastre than O(sqrt(N))

Послано Leonid Volkov 20 мар 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!

Обсуждение задачи 1204. Идемпотенты