Posted: Fri Mar 14, 2008 5:12 pm
Thank you very much !
My problem was an overflow, because I didn't used doubles.
But now I got accepted
My problem was an overflow, because I didn't used doubles.
But now I got accepted
Hmm...don't you have to check for all i=2..N/2 for each input N? Wouldn't that time out?sunny wrote:My solution is little different.
You can see that,
for all i's <= N/2 there are S[N/i] pairs where gcd=i.
where, S[k] means the total number of relatively prime pairs less than or equal to k. Or it can be written:
S[k]= phi(2] + phi(3) + ......+ phi(k)
phi(n) = the number of reltively primes less than n.
As there can be S[N/i] pairs where gcd=i, so i should be multiplied S[N/i] times. You just need to calculate log(i^S[N/i]) for all i's<=N/2.