Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
Euler's totient function (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 2
  • Trang:
  • << < 1 2 > >>
CHỦ ĐỀ - Euler's totient function
#13422
Heo mập (Admin)
phaleq+44
Admin
Bài viết: 680
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Euler's totient function 11 năm, 10 tháng trước   (+0)
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/
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#13423
minhduc (Admin)
paulmcvn+71
Admin
Bài viết: 1288
graphgraph
Thành viên đang truy cập Click vào đây để xem thông tin về thành viên này
Trả lời: Euler's totient function 11 năm, 10 tháng trước   (+0)
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);
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#13424
Heo mập (Admin)
phaleq+44
Admin
Bài viết: 680
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Euler's totient function 11 năm, 10 tháng trước   (+0)
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?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#13425
minhduc (Admin)
paulmcvn+71
Admin
Bài viết: 1288
graphgraph
Thành viên đang truy cập Click vào đây để xem thông tin về thành viên này
Trả lời: Euler's totient function 11 năm, 10 tháng trước   (+0)
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
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#13439
Heo mập (Admin)
phaleq+44
Admin
Bài viết: 680
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Euler's totient function 11 năm, 10 tháng trước   (+0)
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?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#13440
minhduc (Admin)
paulmcvn+71
Admin
Bài viết: 1288
graphgraph
Thành viên đang truy cập Click vào đây để xem thông tin về thành viên này
Trả lời: Euler's totient function 11 năm, 10 tháng trước   (+0)
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}
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#13444
Heo mập (Admin)
phaleq+44
Admin
Bài viết: 680
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Euler's totient function 11 năm, 10 tháng trước   (+0)
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?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#13445
minhduc (Admin)
paulmcvn+71
Admin
Bài viết: 1288
graphgraph
Thành viên đang truy cập Click vào đây để xem thông tin về thành viên này
Trả lời: Euler's totient function 11 năm, 10 tháng trước   (+0)
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.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#13450
Heo mập (Admin)
phaleq+44
Admin
Bài viết: 680
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Euler's totient function 11 năm, 9 tháng trước   (+0)
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)
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#13451
minhduc (Admin)
paulmcvn+71
Admin
Bài viết: 1288
graphgraph
Thành viên đang truy cập Click vào đây để xem thông tin về thành viên này
Trả lời: Euler's totient function 11 năm, 9 tháng trước   (+0)
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.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
  • Trang:
  • << < 1 2 > >>
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS