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

### 11424 - GCD - Extreme (I)

Posted: **Sun Mar 16, 2008 5:19 pm**

by **f74956227**

How can i solve this problem? can someone give me some hints, plz

i always get tle... and i can't use 200000*200000 array...

Posted: **Sun Mar 16, 2008 5:39 pm**

by **mf**

Hint: use

Euler's totient function.

And sieve of Eratosthenes to quickly compute a table of its values.

Posted: **Sun Mar 16, 2008 6:37 pm**

by **f74956227**

OH...i still don't know how to use sieve to find T(n) (totient number of n)

i use sieve to find prime and use them to find prime factor of n, then by

T(n)=N*(1-1/p1)(1-1/p2)...

(p1 p2 ... is the prime factor of n) could you please tell me how to use sieve to find the totient number?? sorry >"<

Posted: **Sun Mar 16, 2008 7:02 pm**

by **helloneo**

Posted: **Sun Mar 16, 2008 7:05 pm**

by **emotional blind**

T(n)=N*(1-1/p1)(1-1/p2)...

reorganize this equation

if n = p1^k1 * p2^k * ...

then T(n) = ( p1^k - P1^(k-1) ) * ( p2^k - P2^(k-1) ) * ...

from this equation it is easy to realize how sieve will do. initialize table with 1. and for every prime factor of n., T[n] will be hit once, and multiply it by p^k - p^(k-1) .

Posted: **Mon Mar 17, 2008 2:13 pm**

by **f74956227**

How can i use the sum of GCD funciton Sum_{d|n} d*phi(n/d), where phi(n) is Euler totient function by finding the d that d|n

Now i find the totient function but I still don't know how to use the function..

Posted: **Mon Mar 17, 2008 2:53 pm**

by **mf**

phi(n) is number of integers 1<=m<=n, such that gcd(n, m) = 1 -- this is just the definition of phi. Number of pairs (x, y) such that gcd(x, y) = 1, and 1<=x<y<=n is then the sum a[n] = phi(2) + phi(3) + ... + phi(n).

Number of pairs (x, y), such that gcd(x, y) = d is the same as the number of relatively-prime pairs (x', y'), such that 1 <= x' < y' <= n/d, and that's just a[n/d]. ("/" is the quotient of division, as in C.)

Now, the sum in the problem statement is just 1*a[n/1] + 2*a[n/2] + 3*a[n/3] + ... + n*a[n/n]. This formula is enough for 11426, but I've got a TLE with it on 11424. One way to optimize is to notice that there are at most 2*sqrt(n) distinct values that quotient n/i can take, and cleverly iterate just over them.

Posted: **Mon Mar 17, 2008 3:12 pm**

by **Robert Gerbicz**

mf wrote:
Now, the sum in the problem statement is just 1*a[n/1] + 2*a[n/2] + 3*a[n/3] + ... + n*a[n/n]. This formula is enough for 11426, but I've got a TLE with it on 11424. One way to optimize is to notice that there are at most 2*sqrt(n) distinct values that quotient n/i can take, and cleverly iterate just over them.

It is possible to compute the whole array! For this study what is

You can build up the G array up to N in O(N*log(N)) time and O(N) memory.

For example: up to N=200000 it took 0.11 sec. and for N=4000000 it took 3.13 sec., so within the timelimit. I've used this on the contest.

### Got TLE...

Posted: **Tue Mar 18, 2008 12:11 pm**

by **Obaida**

How I could reduce time here... Some one please help me...

### Re: Got TLE...

Posted: **Tue Mar 18, 2008 1:59 pm**

by **sunny**

Obaida wrote:How I could reduce time here... Some one please help me...

You can't get AC with a O(N^2) algorithm. Read the previous posts carefully to get an idea of an efficient solution.

Posted: **Tue Mar 18, 2008 5:35 pm**

by **f74956227**

FIND_totient();

a[0]=a[1]=0,a[2]=1;

for(i=3;i<MAX;i++)

{

/*--caculate the sum(i=1,n-1,gcd(i,n)) --*/

m=i/2;

a

*=a[i-1];*

for(j=1;j<=m;j++)

{

if(i%j==0)

a*+=j*totient[i/j]; *

}

}

I use a table to store the number by a[n]-a[n-1]=sum(i=1,n-1,gcd(i,n)) , but is still too slow... can someone help me plz

Posted: **Tue Mar 18, 2008 9:53 pm**

by **Robert Gerbicz**

f74956227 wrote:
I use a table to store the number by a[n]-a[n-1]=sum(i=1,n-1,gcd(i,n)) , but is still too slow... can someone help me plz

Your code is still slow and bad. Here it is my (first) method with more details in pseudocode:

Code: Select all

```
compute eulerphi in [1,N] by sieving (it can be done in O(N*loglog(N)) time)
(type of G array is long long int)
for k=1 to k=N let G[k]=0
for k=1 to k=N
for n=2*k to n=N step k let G[n]+=k*eulerphi[n/k]
for k=2 to k=N let G[k]+=G[k-1]
and now you're ready: G[n]=sum(i=1,n,sum(j=i+1,n,gcd(i,j)) for every 1<=n<=N integer.
```

Posted: **Wed Mar 19, 2008 1:43 am**

by **f74956227**

Yaaaaa i got AC by your method,

really thank you!!!

now i am trying 1 am trying 10426 but always runtime error QQ by the same algorithm with MAX = 4000100 and long long a[MAX]

memset(a,0,MAX*sizeof(int));

for(i=1;i<MAX;i++)

for(j=2*i;j<MAX;j+=i)

a[j]+=i*totient[j/i];

for(i=2;i<MAX;i++)

a

*+=a[i-1];*

what's wrong...

Posted: **Wed Mar 19, 2008 2:28 am**

by **Robert Gerbicz**

f74956227 wrote:
now i am trying 1 am trying 10426 but always runtime error QQ by the same algorithm with MAX = 4000100 and long long a[MAX]

You need to declare them in dynamic way, otherwise you run out of judge's heap (it was 8 MB on the old judge), so to avoid RTE you need to do:

Code: Select all

```
int *eulerphi;
long long int **G;
eulerphi=(int*) (malloc) ((MAX+1)*sizeof(int));
G=(long long int*) (malloc) ((MAX+1)*sizeof(long long int));
```

And don't forget to include also stdlib.h for this.

Posted: **Wed Mar 19, 2008 7:27 am**

by **f74956227**

Thank you Robert, i get ac now

with 3.75 second, i saw your 0.050 rank...

it is so fast...

^^ thank for your hints!