11317 - GCD+LCM

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

New poster
Posts: 11
Joined: Sat Dec 29, 2007 2:39 pm

Post by Brainless »

Thank you very much !

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

But now I got accepted :)
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States


Post by yiuyuho »

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.
Hmm...don't you have to check for all i=2..N/2 for each input N? Wouldn't that time out?
Post Reply

Return to “Volume 113 (11300-11399)”