## 11317 - GCD+LCM

Moderator: Board moderators

fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm

### 11317 - GCD+LCM

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

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:
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])``````

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:
Can you give more description.
also what is C and G?
Sleep enough after death, it is the time to work.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:
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 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 ).
Last edited by Robert Gerbicz on Sun Oct 21, 2007 5:15 pm, edited 4 times in total.

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:
THANKS SO MUCH.
I will start now .
Sleep enough after death, it is the time to work.

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET
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.

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:
To sunny

can u describe me more?

Thanks
Keep posting
Sapnil
"Dream Is The Key To Success"

@@@ Jony @@@

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:
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.
Sleep enough after death, it is the time to work.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Use Euler function.

----
Rio

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:
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.
Sleep enough after death, it is the time to work.

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET
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.

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:
To Sunny

Thank u sunny,its really Help me.

Thanks
Keep posting
Sapnil
"Dream Is The Key To Success"

@@@ Jony @@@

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:
Big Thanks sunny, so cute idea.
Sleep enough after death, it is the time to work.

Brainless
New poster
Posts: 11
Joined: Sat Dec 29, 2007 2:39 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 !

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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.