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

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

11317 - GCD+LCM

Post by fpavetic » 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

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by Robert Gerbicz » 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])

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 » Sun Oct 21, 2007 4:18 pm

Can you give more description.
also what is C and G?
Sleep enough after death, it is the time to work.
Mostafa Saad

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by Robert Gerbicz » 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 ).
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:

Post by 898989 » Sun Oct 21, 2007 5:05 pm

THANKS SO MUCH.
I will start now .
Sleep enough after death, it is the time to work.
Mostafa Saad

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny » 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.

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

Post by sapnil » Mon Oct 22, 2007 1:59 pm

To sunny

I can't get your point...
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:

Post by 898989 » 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.
Sleep enough after death, it is the time to work.
Mostafa Saad

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Tue Oct 23, 2007 6:09 am

Use Euler function.

----
Rio

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 » 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.
Sleep enough after death, it is the time to work.
Mostafa Saad

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny » 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.

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

Post by sapnil » Tue Oct 23, 2007 2:56 pm

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:

Post by 898989 » Tue Oct 23, 2007 3:13 pm

Big Thanks sunny, so cute idea.
Sleep enough after death, it is the time to work.
Mostafa Saad

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

Post by Brainless » 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 !

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » 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.

Post Reply

Return to “Volume 113 (11300-11399)”