All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.
Moderator: Board moderators
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.