11424  GCD  Extreme (I)
Moderator: Board moderators
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...
i always get tle... and i can't use 200000*200000 array...
Hint: use Euler's totient function.
And sieve of Eratosthenes to quickly compute a table of its values.
And sieve of Eratosthenes to quickly compute a table of its values.

 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:
T(n)=N*(11/p1)(11/p2)...
reorganize this equation
if n = p1^k1 * p2^k * ...
then T(n) = ( p1^k  P1^(k1) ) * ( p2^k  P2^(k1) ) * ...
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^(k1) .
reorganize this equation
if n = p1^k1 * p2^k * ...
then T(n) = ( p1^k  P1^(k1) ) * ( p2^k  P2^(k1) ) * ...
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^(k1) .
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 relativelyprime 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.
Number of pairs (x, y), such that gcd(x, y) = d is the same as the number of relativelyprime 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.

 Experienced poster
 Posts: 196
 Joined: Wed May 02, 2007 10:12 pm
 Location: Hungary, Pest county, Halasztelek
 Contact:
It is possible to compute the whole array! For this study what ismf 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.
Code: Select all
G[n]G[n1]=sum(i=1,n1,gcd(i,n))
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...
How I could reduce time here... Some one please help me...
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.
This may be the address of success.
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.Obaida wrote:How I could reduce time here... Some one please help me...

 Experienced poster
 Posts: 196
 Joined: Wed May 02, 2007 10:12 pm
 Location: Hungary, Pest county, Halasztelek
 Contact:
Your code is still slow and bad. Here it is my (first) method with more details in pseudocode:f74956227 wrote: I use a table to store the number by a[n]a[n1]=sum(i=1,n1,gcd(i,n)) , but is still too slow... can someone help me plz
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[k1]
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.
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[i1];
what's wrong...
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[i1];
what's wrong...

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