11317 - GCD+LCM

[Brainless]

Thank you very much !

My problem was an overflow, because I didn't used doubles.

But now I got accepted

[yiuyuho]

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.

Hmm...don't you have to check for all i=2..N/2 for each input N? Wouldn't that time out?