Page 1 of 2

### 11317 - GCD+LCM

Posted: Sun Oct 21, 2007 12:19 pm
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
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
Can you give more description.
also what is C and G?

Posted: Sun Oct 21, 2007 5:00 pm
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
THANKS SO MUCH.
I will start now .

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

can u describe me more?

Thanks
Keep posting
Sapnil

Posted: Mon Oct 22, 2007 9:22 pm
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
Use Euler function.

----
Rio

Posted: Tue Oct 23, 2007 10:44 am
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
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
To Sunny

Thank u sunny,its really Help me.

Thanks
Keep posting
Sapnil

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

Posted: Sun Mar 09, 2008 12:33 pm
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
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.