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
[N] Lời giải mẫu cho một số bài (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 0
CHỦ ĐỀ - [N] Lời giải mẫu cho một số bài
#11694
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
[N] Lời giải mẫu cho một số bài 11 năm, 11 tháng trước   (+0)
Do hiện nay chưa có topic thảo luận về các bài trong project N nên mình mở đầu một số topic.
Chú ý: các bạn vui lòng không post câu trả lời trong topic này. Thứ hai là cố gắng suy nghĩ bài toán trước khi vào đọc lời giải.

Bài 21: Tìm 9 chữ số cuối cùng của 3^(29!)
Bạn cần tính 3^(29!) mod 10^9
Nhận thấy ngay 3^(29!) = (((3^1)^2)^3)^..29,
vì vậy bạn chỉ cần làm cách đơn giản nhất sử dụng 1 + 2 + ... + 29 phép tính nhân là cũng tìm được kết quả

Bài 24 Tính ⱷ(9876543210).
Bạn tìm cách xây dựng công thức tính hàm ⱷ(n). Muốn vậy cần đi từ các trường hợp đơn giản nhất là n = p và n=p^k với p là số nguyên tố.
* Ta thấy: với p là số nguyên tố ⱷ(p) = p-1, vì 1, 2, ... ,p-1 đều nguyên tố cùng nhau với p
* ⱷ(p^k) = ?
Các số không nguyên tố cùng nhau với p^k từ 1 đến p^k là: p, 2p, 3p, ... ,p^(k-1)p, tổng cộng có p^(k-1) số.
Do đó ⱷ(p^k)=p^k - p^(k-1)
* Tiếp theo bạn cần chứng minh là: nếu a, b nguyên tố cùng nhau thì ⱷ(ab) = ⱷ(a) * ⱷ(b)
Để chứng minh được điều này cần sử dụng định lý đồng dư Trung Hoa, phát biểu như sau:
nếu x=a(mod m) và x=b(mod n), với (m,n)=1
thì tồn tại duy nhất c, 0<=c<mn sao cho x=c(mod mn)
* Từ đó suy ra công thức ⱷ(n)=SUM((pi^ki - pi^(ki-1)) với n=p1^k1*p2^k2*..*pm^km là biểu diễn nguyên tố của số n
Như vậy chi phí để tính ⱷ(n) là khoảng O(sqrt(n))
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#11821
phamnamlong (Thành viên)
phamnamlong
Biết code binary-indexed tree
Bài viết: 47
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: [N] Lời giải mẫu cho một số bài 11 năm, 11 tháng trước   (+0)
Kí tự "phi" bị hỏng kìa. (Sửa xong thì cậu xoá bài post này đi cho đẹp topic nhé :d)
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#11834
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: [N] Lời giải mẫu cho một số bài 11 năm, 11 tháng trước   (+0)
Trong Windows có nhiều loại "phi" quá:ɸΦφϕᵠᵩᶲⱷ nên tớ chọn đại
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#11887
buihaduong (Thành viên)
buihaduong
Biết code binary-indexed tree
Bài viết: 40
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: [N] Lời giải mẫu cho một số bài 11 năm, 11 tháng trước   (+0)
Anh Đức có thể hướng dẫn một chút về phương trình đồng dư được ko anh ?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#11890
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: [N] Lời giải mẫu cho một số bài 11 năm, 11 tháng trước   (+0)
Em có thể đọc các bài viết về số học trong thư viện, có đề cập đến PT đồng dư.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#12787
tung (Thành viên)
whiterose
Đã biết code đệ quy
Bài viết: 15
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: [N] Lời giải mẫu cho một số bài 11 năm, 10 tháng trước   (+0)
Ham tinh Phi: (code suu tam)
Code:
 
void Eulerphi(void)
{
  register int i, j;
  for (i = 1; i <= MAX; i+=2) eulerphi[i] = i;
  eulerphi[2] = 1;
//  memset(prime, 0, sizeof(prime));
  for (j = 4; j <= MAX; j += 2) prime[j] = 1, eulerphi[j] = j/2;
  for (i = 3; i <= MAX; i += 2) 
  {
    if (prime[i]) continue;
    eulerphi[i] -= eulerphi[i] / i;
    for (j = i+i; j <= MAX; j += i) prime[j] = 1, eulerphi[j] -= eulerphi[j] / i;
  }
}
Do phuc tap la O(nloglogn) thi phai. Sorry ko go dc tieng viet
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#12790
tung (Thành viên)
whiterose
Đã biết code đệ quy
Bài viết: 15
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: [N] Lời giải mẫu cho một số bài 11 năm, 10 tháng trước   (+0)
Ham nay tinh Phi[1..N]. Minh thay doan code nay kha hay, co the ung dung giai rat nhieu bai
 
Đã 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
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