Mất mật khẩu? | Đăng ký Nhập các thuật ngữ tìm kiếm của bạn Web VNOI Nộp mẫu đơn tìm kiếm ### Đ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
Forum  Thảo luận chung  English corner
Euler's totient function (1 đang xem) ,(1) Khách  Được ưa thích: 2 Trang: << < 1 2 > >>
CHỦ ĐỀ - Euler's totient function
#13422
phaleq+44  Bài viết: 680    Euler's totient function 11 năm, 10 tháng trước   (+0)
Hi, anybody knows how to compute all phi, phi, .., 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
Đã khóa chức năng gửi bài.
#13423
paulmcvn+71  Bài viết: 1288    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; 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
Đã khóa chức năng gửi bài.
#13424
phaleq+44  Bài viết: 680    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
Đã khóa chức năng gửi bài.
#13425
paulmcvn+71  Bài viết: 1288    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
Đã khóa chức năng gửi bài.
#13439
phaleq+44  Bài viết: 680    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
Đã khóa chức năng gửi bài.
#13440
paulmcvn+71  Bài viết: 1288    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
Đã khóa chức năng gửi bài.
#13444
phaleq+44  Bài viết: 680    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
Đã khóa chức năng gửi bài.
#13445
paulmcvn+71  Bài viết: 1288    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
Đã khóa chức năng gửi bài.
#13450
phaleq+44  Bài viết: 680    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...G[N] in O(N). Detail: G[p^k] = (k+1)*p^k - k*p^(k-1)  Đã lưu IP
Đã khóa chức năng gửi bài.
#13451       Đã lưu IP  Trang: << < 1 2 > >>
 Mục lục diễn đàn Thảo luận chung English corner