10299 - Relatives

Wei-Ming Chen · Post by **Wei-Ming Chen** » Sat Jan 28, 2006 11:02 am

Got AC now, thanks everyone's help.

mamun · Post by **mamun** » Sat Jan 28, 2006 12:47 pm

Precalculate the prime numbers.

Wei-Ming Chen · Post by **Wei-Ming Chen** » Sat Jan 28, 2006 3:40 pm

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

mamun · Post by **mamun** » 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.

Wei-Ming Chen · Post by **Wei-Ming Chen** » Sun Jan 29, 2006 6:49 am

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

helloneo · Post by **helloneo** » 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..

Wei-Ming Chen · Post by **Wei-Ming Chen** » Sun Jan 29, 2006 12:34 pm

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

Amir Aavani · Post by **Amir Aavani** » 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.

Ankur Jaiswal · Post by **Ankur Jaiswal** » 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

.

serur · Post by **serur** » 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...

Ankur Jaiswal · Post by **Ankur Jaiswal** » 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.

serur · Post by **serur** » 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.

Ankur Jaiswal · Post by **Ankur Jaiswal** » 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.

mamun · Post by **mamun** » 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).

Ankur Jaiswal · Post by **Ankur Jaiswal** » 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