11317 - GCD+LCM

[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

[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])

[898989]

Can you give more description.
also what is C and G?

[Robert Gerbicz]

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 ).

[898989]

THANKS SO MUCH.
I will start now .

[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.

[sapnil]

To sunny

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

Thanks
Keep posting
Sapnil

[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.

[rio]

Use Euler function.

----
Rio

[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.

[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.

[sapnil]

To Sunny

Thank u sunny,its really Help me.

Thanks
Keep posting
Sapnil

[898989]

Big Thanks sunny, so cute idea.

[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 !

[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.