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
Trả lời: 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Ủ ĐỀ - Trả lời: Euler's totient function
#13453
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)
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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#13454
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)
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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#13455
khuc_tuan (Admin)
khuc_tuan+137
Admin
Bài viết: 1472
graph
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)
Two admins shoot each other in an impressive thread
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#13459
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)
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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#15396
ultimate (Thành viên)
huedang-
Nhắm mắt code không bug
Bài viết: 179
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, 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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#15419
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, 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 Đã 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