OJ Board

Posted: **Sat Jan 28, 2006 11:02 am**

Got AC now, thanks everyone's help.

Posted: **Sat Jan 28, 2006 12:47 pm**

Precalculate the prime numbers.

Posted: **Sat Jan 28, 2006 3:40 pm**

I fixed my code, but it changed to WA now.....
Can you help again?

Posted: **Sat Jan 28, 2006 5:49 pm**

You have to take care of more number of primes. For example, output of

Code: Select all

997485889
998623201
999002449

are

Code: Select all

997454306
998591600
998970842

Use code tagging for posting codes.

Posted: **Sun Jan 29, 2006 6:49 am**

I changed my code.
But why TLE again?
Should I make a int x[1000000000] ?

Posted: **Sun Jan 29, 2006 7:12 am**

Wei-Ming Chen wrote:I changed my code.
But why TLE again?
Should I make a int x[1000000000] ?

nope..
sqrt(1000000000) will be enough..

Posted: **Sun Jan 29, 2006 12:34 pm**

Maybe I should think why I used sqrt(1000000000) and got TLE.......

Posted: **Tue Mar 28, 2006 1:06 pm**

one of your code problem is that num must be longint,
because, the problem states that n<1000000000.

Posted: **Mon May 01, 2006 12:45 am**

I have used sieve to calculate the prime numbers. Then I used Euler's fonction to calculate the number of relatives.
Then too I am getting TLE.
Smbd help me.
Thanx in advance.
Code :
Removed after accpeted

.

Posted: **Mon May 01, 2006 9:07 am**

Dear - Ankur Jaiswal!

Euler Phi-function works fine here - I did got AC, but long after series of TLE too...

Posted: **Mon May 01, 2006 6:01 pm**

I too have used Euler Phi function to solve this question.
But I first calculated prime numbers using Sieve so as to get the prime numbers in lesser time. But then too i am getting TLE. Plz give more hints to solve this problem.

Posted: **Mon May 01, 2006 8:02 pm**

Clever brute-force check (however weird it sounds

) is enough - get rid of factor 2 and run odds. Don't forget about square roots. And also that this algo not necesarily terminates with 1.

Posted: **Tue May 02, 2006 9:31 am**

When num!=1 (but i>3401) in the function relatives() and the for loop is done with, then i am keeping a check onto num (whether it is 1 or not).
If it is not 1 then it will obviously be a prime number... therefore i have done ans=(ans/num) *(num-1);
so i dont think that this condition is wrong.

Posted: **Tue May 02, 2006 9:59 am**

You can improve your euler phi calculation. Instead of trying with all the prime numbers, try with the prime numbers that are <= sqrt(num).

Posted: **Tue May 02, 2006 11:17 am**

thanks a lot.
But now i am getting WA.

OJ Board

10299 - Relatives

10299 TLE... (now WA) -> TLE again

10299 TLE

Solution to 10299

Terminating condition on (num==1)

Solution