Hi, anybody knows how to compute all phi[1], phi[2], .., phi[n] in O(n*log log n)?

Here phi[i] = Euler's totient function of i.
For more details: http://en.wikipedia.org/wiki/Euler%27s_totient_function

I know an algorithm to compute them using sieve:

Code:

const int N = 1000000; int phi[N+1]; int main() { for (int n = 1; n <= N; ++ n) phi[n] = n; for (int i = 1; i <= N; ++ i) for (int n = i + i; n <= N; n += i) phi[n] -= phi[i]; }

but it's not fast enough to solve this problem: http://vn.spoj.pl/problems/GCDSUM/

You only need to consider the prime divisors:

Code:

phi[1]=1; for (int i=2; i<=n; ++i) phi[i]=i; for (int i=2; i<=n; ++i) if (phi[i]==i) // prime for (int j=i; j<=n; j+=i) phi[j]=phi[j]/i*(i-1);

Thank you, brother Duc!
But I still got TLE

How about this sieve that calculates G[n] = sum( gcd(j, n) ) | j = 1, 2, ..., n ?

Code:

for (int n = 1; n <= N; ++ n) G[n] = 0; for (int d = 1; d <= N; ++ d) for (int n = d + d; n <= N; n += d) G[n] += (long long) d * phi[n/d];

Any hints to improve it?

Computing G[n] is not the correct way to solve this problem
After computing phi[1..n], you can solve the problem in O(n)

Hint: look at problem N45

Computing G[n] is one of the ways to solve the problem in O(n)
Maybe your solution is another one

Anyway, I can't find the idea behind the problem N45.
- In N44, it's easy to calculate coprime(n) = 2*sum(phi(i))+1 (i = 2,3,..,n). But we can't do the same in N45 because n is too big.
- If we can compute coprime(n), we know the number of pairs (i, j) that satisfy (1 <= i,j <= n) and gcd(i, j) = 1. But how about the others? How can we know the number of pairs (u, v) such that gcd(u, v) = d?

And the BIG question:
How can we solve the problems in O(N) by this approach?

Nuga viết:

QUOTE:

- In N44, it's easy to calculate coprime(n) = 2*sum(phi(i))+1 (i = 2,3,..,n). But we can't do the same in N45 because n is too big.
- If we can compute coprime(n), we know the number of pairs (i, j) that satisfy (1 <= i,j <= n) and gcd(i, j) = 1. But how about the others? How can we know the number of pairs (u, v) such that gcd(u, v) = d?

1. You can use the above formula, since I just show yow how to compute phi[1..n] in O(nloglogn).
2. #{1<=a,b<=n; (a,b)=d} = #{1<=a,b<=n/d | (a,b)=1}

minhduc viết:

QUOTE:

1. You can use the above formula, since I just show yow how to compute phi[1..n] in O(nloglogn).

Which formula?
You mean that we have a formula similar to the formula of phi?


minhduc viết:

QUOTE:

2. #{1<=a,b<=n; (a,b)=d} = #{1<=a,b<=n/d | (a,b)=1}

Exactly the same as a property of phi.

So, if we define f(n) = sum(phi(i)) | i = 2 -> n, the result of the GCDSUM problem can be written as:
gcdsum(n) = sum(d*f(n/d)) | d = 1 -> n (*)

Right?

Now we have to solve (*) in O(n) How?

Actually is (*) already in O(n) You can solve each query in O(n) to pass this problem. Just read an n and compute gcdsum(n); you don't need to compute all of them.
(*) can also be computed in O(logn). Hint: grouping the terms accoring to the value of (n/d), in the same way as problem N40 and N41.

Right. To solve GCDSUM, we don't need to compute all gcdsum(n).
But to solve http://www.spoj.pl/problems/GCDEX/, we have to.
Maybe computing gcdsum(n) in O(logn) is quite complicated

Anyway, we can use this approach of gerben to compute all gcdsum(n) in O(n):

As I stated above:
G[n] = sum( gcd(j, n) ) | j = 1, 2, ..., n
G[n] = sum( d*phi[n/d] ) for every d|n

If you define G[n]=sum(d*phi[n/d]), where d runs over all divisors including n. Then we have G[n*m]=G[n]*G[m] if gcd(n,m)=1 by the chinese remainder theorem and the fact phi also satisfy this property.

This means if we perform a sieve of erastosthenes to find for each number n the largest prime p that divides this n. Then n=p^k*m, gcd(p,m)=1 and thus G[n]=G[p^k]*G[m]. There is a formula for G[p^k]. This way you can calculate all the G[1]...G[N] in O(N).

Detail: G[p^k] = (k+1)*p^k - k*p^(k-1)

Not complicated at all, look at problem N40 and N41!
Hint: how to compute (n div 1) + (n div 2) + ... + (n div n) in O(logn)?
Hmm I think for GCDEX O(logn) is quite ok, but let me think about O(n) approach

Yes, the above method is correct.
An artihmetic function f(n) that satisfies f(mn) = f(m)f(n) for (m,n)=1 is called a multiplicative function. For any multiplicative function f that has an easy way to compute f(p^k), you could compute f[1..n] in O(nloglogn) using the sieve of Erasthosenes.
You may want to try SPOJ DIVSUM with this method.