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
Trả lời: Euler's totient function (1 đang xem) ,(1) Khách  Được ưa thích: 2 Trang: << < 1 2 > >>
CHỦ ĐỀ - Trả lời: Euler's totient function
#13453
paulmcvn+71  Bài viết: 1288    Trả lời: Euler's totient function 11 năm, 9 tháng trước (+0) If you're interested in Number Theory, you may want to try this "interesting" problem: http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2600 Đã lưu IP
Đã khóa chức năng gửi bài.
#13454
phaleq+44  Bài viết: 680    Trả lời: Euler's totient function 11 năm, 9 tháng trước   (+0)
minhduc viết:
QUOTE:

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.

Yeah, multiplicative functions are interesting! QUOTE:
Hint: how to compute (n div 1) + (n div 2) + ... + (n div n) in O(logn)?

I find that complicated For example n = 10: computing S = sum(n div d) | d = 1,2,...,n
 Code: ```  d: 1 2 3 4 5 6 7 8 9 10 n/d: 10 5 3 2 2 1 1 1 1 1 (*) ```
Here, how to group the terms (in (*)) that share the same value of n/d?  Đã lưu IP
Đã khóa chức năng gửi bài.
#13455
khuc_tuan+137  Bài viết: 1472   Trả lời: Euler's totient function 11 năm, 9 tháng trước (+0) Two admins shoot each other in an impressive thread  Đã lưu IP
Đã khóa chức năng gửi bài.
#13459
paulmcvn+71  Bài viết: 1288    Trả lời: Euler's totient function 11 năm, 9 tháng trước   (+0)
That's good to improve the English contents of our page Well, to compute (n div 1) + (n div 2) + ... + (n div n):
 Code: ```  int64 s=0; for (int64 i=1; i<=n; ) { int64 q=n/i, r=n/q; s+=(int64)(r-i+1)*q; i=r+1; } return s;```
In the above code, n div i=n div (i+1)=...=n div r = q In (*), the grouping is exactly the same Đã lưu IP
Đã khóa chức năng gửi bài.
#15396
(Thành viên)
huedang- Nhắm mắt code không bug Bài viết: 179    Trả lời: Euler's totient function 11 năm, 7 tháng trước (+0) Thank you very much, admin minhduc Can we use this to compute (n mod 1) + (n mod 2) + ... + (n mod n), for (n mod i) = n - (n div i)*i ? Đã lưu IP
Đã khóa chức năng gửi bài.
#15419      Trả lời: Euler's totient function 11 năm, 7 tháng trước (+0) ultimate viết: QUOTE:Thank you very much, admin minhduc :) Can we use this to compute (n mod 1) + (n mod 2) + ... + (n mod n), for (n mod i) = n - (n div i)*i ? Yes, it's quite similar  Đã lưu IP  Trang: << < 1 2 > >>
 Mục lục diễn đàn Thảo luận chung English corner