11317 - GCD+LCM
Moderator: Board moderators
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
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
-
- 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])
-
- Experienced poster
- Posts: 196
- Joined: Wed May 02, 2007 10:12 pm
- Location: Hungary, Pest county, Halasztelek
- Contact:
G[n] is the gcd product in the description, so898989 wrote:Can you give more description.
also what is C and G?
Code: Select all
G[n]=prod(i=1,n-1,prod(j=i+1,n,gcd(i,j)))
Code: Select all
C[1]=1 and C[n]=G[n]/G[n-1] for n>1
Code: Select all
G[n]=C[n]*G[n-1]
To compute the lcm values use that
Code: Select all
gcd(a,b)*lcm(a,b)=a*b
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])
Last edited by Robert Gerbicz on Sun Oct 21, 2007 5:15 pm, edited 4 times in total.
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.
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.
suppose, N=8, i=2
now, all the pairs where gcd=2 are:
And all these are relative prime pairs less then or equal to N/2 before multiplied by 2.
can be written :
You just need to calculate the S[] efficiently.
now, all the pairs where gcd=2 are:
Code: Select all
(2,4),(2,6),(2,8),(4,6),(6,8)
can be written :
Code: Select all
2* ( (1,2),(1,3),(1,4),(2,3),(3,4) )
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:
My output:
Thanks !
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
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
My accepted code returns..
Output:
Hope these help.
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