11424 - GCD - Extreme (I)

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

[mf]

Hint: use Euler's totient function.
And sieve of Eratosthenes to quickly compute a table of its values.

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

[helloneo]

This thread may help you..?

http://online-judge.uva.es/board/viewtopic.php?t=9952

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

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

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

[Robert Gerbicz]

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]

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

Code: Select all

Removed

[sunny]

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.

[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

[Robert Gerbicz]

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]

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]

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]

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!