Page **1** of **2**

### 11317 - GCD+LCM

Posted: **Sun Oct 21, 2007 12:19 pm**

by **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

Posted: **Sun Oct 21, 2007 12:47 pm**

by **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])
```

Posted: **Sun Oct 21, 2007 4:18 pm**

by **898989**

Can you give more description.

also what is C and G?

Posted: **Sun Oct 21, 2007 5:00 pm**

by **Robert Gerbicz**

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

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

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

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**

by **898989**

THANKS SO MUCH.

I will start now .

Posted: **Sun Oct 21, 2007 10:28 pm**

by **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.

Posted: **Mon Oct 22, 2007 1:59 pm**

by **sapnil**

To sunny

I can't get your point...

can u describe me more?

Thanks

Keep posting

Sapnil

Posted: **Mon Oct 22, 2007 9:22 pm**

by **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.

Posted: **Tue Oct 23, 2007 6:09 am**

by **rio**

Use Euler function.

----

Rio

Posted: **Tue Oct 23, 2007 10:44 am**

by **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. *

Posted: **Tue Oct 23, 2007 2:46 pm**

by **sunny**

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 :

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**

by **sapnil**

To Sunny

Thank u sunny,its really Help me.

Thanks

Keep posting

Sapnil

Posted: **Tue Oct 23, 2007 3:13 pm**

by **898989**

Big Thanks sunny, so cute idea.

Posted: **Sun Mar 09, 2008 12:33 pm**

by **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 !

Posted: **Mon Mar 10, 2008 1:03 am**

by **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.