## 11424 - GCD - Extreme (I)

Moderator: Board moderators

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

### 11424 - GCD - Extreme (I)

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Hint: use Euler's totient function.
And sieve of Eratosthenes to quickly compute a table of its values.

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:
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 >"<

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
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) .

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:
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..

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:
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

Code: Select all

``````G[n]-G[n-1]=sum(i=1,n-1,gcd(i,n))
``````
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.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Got TLE...

Code: Select all

``Removed``
Last edited by Obaida on Sun May 25, 2008 10:21 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

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

### Re: Got TLE...

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

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact: FIND_totient();
a=a=0,a=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

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:
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.
``````

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:
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...

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:
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.

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:
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! 