Page 1 of 2

11317 - GCD+LCM

Posted: Sun Oct 21, 2007 12:19 pm
by fpavetic
hello,

can anyone please post some hints for the first part of the problem?
if one knows how to solve the first part, second is more or less trivial

Filip

Posted: Sun Oct 21, 2007 12:47 pm
by Robert Gerbicz
Determine what is C[n]=G[n]/G[n-1]. By sieving you can compute all log(C[n]) values at once, for this use that if you know the prime factorization of n then you can count the contribution of each prime power to the log(C[n]) value, use that:

Code: Select all

gcd(n,k)=prod(i=1,r,p[i]^min(alpha[i],beta[i])
if n=prod(i=1,r,p[i]^alpha[i]) and k=prod(i=1,r,p[i]^beta[i])

Posted: Sun Oct 21, 2007 4:18 pm
by 898989
Can you give more description.
also what is C and G?

Posted: Sun Oct 21, 2007 5:00 pm
by Robert Gerbicz
898989 wrote:Can you give more description.
also what is C and G?
G[n] is the gcd product in the description, so

Code: Select all

 G[n]=prod(i=1,n-1,prod(j=i+1,n,gcd(i,j)))
I've defined a new C array:

Code: Select all

C[1]=1 and C[n]=G[n]/G[n-1] for n>1
. The advantage is that it is enough to compute only C, because

Code: Select all

 G[n]=C[n]*G[n-1]
So if you can compute C, then by 1,000,000 multiplications you'll get also the required G array.

To compute the lcm values use that

Code: Select all

gcd(a,b)*lcm(a,b)=a*b
I think it's more than enough to write a code.

Ps. Actually we compute only log(G[n]) and log(C[n]) values and in this case

Code: Select all

 log(G[n])=log(C[n])+log(G[n-1])
And don't forget to convert double to long long int when printing the output because the result can be larger than 2^32 ( but smaller than 2^63 for all n<=10^6 ).

Posted: Sun Oct 21, 2007 5:05 pm
by 898989
THANKS SO MUCH.
I will start now .

Posted: Sun Oct 21, 2007 10:28 pm
by sunny
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.

Posted: Mon Oct 22, 2007 1:59 pm
by sapnil
To sunny

I can't get your point...
can u describe me more?

Thanks
Keep posting
Sapnil

Posted: Mon Oct 22, 2007 9:22 pm
by 898989
Hi sunny: In the contest i was trying to know this value S[N/i], but i could not.
How you reach this formula. Any hints for it.

Posted: Tue Oct 23, 2007 6:09 am
by rio
Use Euler function.

----
Rio

Posted: Tue Oct 23, 2007 10:44 am
by 898989
I know Euler function, and solved with it some problems.
I just can not reach to this hint.
for all i's <= N/2 there are S[N/i] pairs where gcd=i.

Posted: Tue Oct 23, 2007 2:46 pm
by sunny
suppose, N=8, i=2
now, all the pairs where gcd=2 are:

Code: Select all

(2,4),(2,6),(2,8),(4,6),(6,8)
And all these are relative prime pairs less then or equal to N/2 before multiplied by 2.
can be written :

Code: Select all

2* ( (1,2),(1,3),(1,4),(2,3),(3,4) )
You just need to calculate the S[] efficiently.

Posted: Tue Oct 23, 2007 2:56 pm
by sapnil
To Sunny

Thank u sunny,its really Help me.

Thanks
Keep posting
Sapnil

Posted: Tue Oct 23, 2007 3:13 pm
by 898989
Big Thanks sunny, so cute idea.

Posted: Sun Mar 09, 2008 12:33 pm
by Brainless
Hello,

I've got the right output for the simple input, but the result of submission is WA.

Can you tell me what is your output with this input ?

Input:

Code: Select all

49872
1000000
197324
230
523789
2
998243
0
My output:

Code: Select all

Case 1: 3076170 102967095
Case 2: 602381204 3515044760
Case 3: 48180480 1844487282
Case 4: 61 959
Case 5: 220969312 1393396619
Case 6: 1 1
Case 7: 598031668 3316376810
Thanks !

Posted: Mon Mar 10, 2008 1:03 am
by Jan
My accepted code returns..

Output:

Code: Select all

Case 1: 3076170 102967095
Case 2: 1237601625 54419431891
Case 3: 48180480 1844487282
Case 4: 61 959
Case 5: 339528555 14159739265
Case 6: 1 1
Case 7: 1233252090 54220763940
Hope these help.