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))

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)

Trong Windows có nhiều loại "phi" quá:ɸΦφϕᵠᵩᶲⱷ nên tớ chọn đại

Anh Đức có thể hướng dẫn một chút về phương trình đồng dư được ko anh ?

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ư.

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

Ham nay tinh Phi[1..N]. Minh thay doan code nay kha hay, co the ung dung giai rat nhieu bai