Hàm Euler và định lý Euler
Hàm Euler φ(n) là số các số từ 1 đến n nguyên tố cùng nhau với n. Ví dụ φ(12) = 4 (các số 1, 5, 7, 11). Hàm này xuất hiện ở rất nhiều bài: đếm phân số tối giản, đếm cặp số nguyên tố cùng nhau, tổng ƯCLN, và quan trọng nhất là định lý Euler, cho phép tính ab mod m với số mũ b khổng lồ và modulo m bất kỳ (không cần là số nguyên tố).
Bài Nguyên lý bù trừ đã có một bài tính φ(n) bằng bù trừ. Bài này đi sâu hơn. Các bạn cần nắm vững bài Số nguyên tố (phân tích thừa số), Sàng Eratosthenes và Lũy thừa nhanh (Fermat nhỏ).
Công thức tính φ(n)
Phần tiêu đề “Công thức tính φ(n)”Nếu n có các ước nguyên tố khác nhau p1, p2, …, pr thì
φ(n) = n × (1 - 1/p1) × (1 - 1/p2) × … × (1 - 1/pr)
Ý nghĩa: trong n số, bỏ đi phần chia hết cho p1 (chiếm 1/p1), rồi phần chia hết cho p2 trong số còn lại, … Ví dụ φ(12) = 12 × (1 - 1/2) × (1 - 1/3) = 12 × 1/2 × 2/3 = 4.
Một vài giá trị đặc biệt:
| n | φ(n) | Lý do |
|---|---|---|
| p nguyên tố | p - 1 | mọi số từ 1 đến p - 1 |
| pk | pk - pk - 1 | bỏ các bội của p |
| a × b với ƯCLN(a, b) = 1 | φ(a) × φ(b) | φ là hàm nhân tính |
def phi(n): kq, p = n, 2 while p * p <= n: if n % p == 0: while n % p == 0: n //= p kq -= kq // p # nhân với (1 - 1/p) p += 1 if n > 1: # còn lại một ước nguyên tố lớn kq -= kq // n return kq
print(phi(12), phi(13), phi(10 ** 12)) # 4 12 400000000000#include <iostream>using namespace std;
long long phi(long long n) { long long kq = n; for (long long p = 2; p * p <= n; p++) { if (n % p == 0) { while (n % p == 0) n /= p; kq -= kq / p; // nhân với (1 - 1/p) } } if (n > 1) kq -= kq / n; // còn lại một ước nguyên tố lớn return kq;}
int main() { cout << phi(12) << " " << phi(13) << " " << phi(1000000000000LL) << endl; return 0;}Chia thử đến căn n, với n = 1012 là khoảng 106 phép chia.
Sàng φ cho mọi số đến N
Phần tiêu đề “Sàng φ cho mọi số đến N”Cần φ của rất nhiều số thì sàng một lần, giống sàng Eratosthenes:
- Gán ph[i] = i với mọi i.
- Duyệt i từ 2 đến N. Nếu ph[i] vẫn bằng i thì i là số nguyên tố (chưa có số nguyên tố nhỏ hơn nào sửa nó). Khi đó với mọi bội j của i: ph[j] = ph[j] - ph[j] / i.
Mỗi số j được “nhân với (1 - 1/p)” đúng một lần cho mỗi ước nguyên tố p của nó.
def sang_phi(N): ph = list(range(N + 1)) for i in range(2, N + 1): if ph[i] == i: # i là số nguyên tố for j in range(i, N + 1, i): ph[j] -= ph[j] // i return ph
print(sang_phi(12)[1:]) # [1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4]#include <iostream>#include <vector>using namespace std;
vector<int> sangPhi(int N) { vector<int> ph(N + 1); for (int i = 0; i <= N; i++) ph[i] = i; for (int i = 2; i <= N; i++) if (ph[i] == i) // i là số nguyên tố for (int j = i; j <= N; j += i) ph[j] -= ph[j] / i; return ph;}
int main() { vector<int> ph = sangPhi(12); for (int i = 1; i <= 12; i++) cout << ph[i] << " "; cout << endl; return 0;}Số phép tính khoảng N × (1/2 + 1/3 + 1/5 + …) với các số nguyên tố đến N, tức cỡ N × log log N, gần như tuyến tính.
Ứng dụng quen thuộc: đặt S(x) = φ(1) + φ(2) + … + φ(x).
- Số phân số tối giản a / b với 0 nhỏ hơn a nhỏ hơn b ≤ N là S(N) - 1.
- Số cặp (x, y) với 1 ≤ x, y ≤ N và ƯCLN(x, y) = 1 là 2 × S(N) - 1.
- Số cặp có ƯCLN đúng bằng d: thay N bằng N // d (vì x = d × a, y = d × b với ƯCLN(a, b) = 1).
Tổng φ trên các ước
Phần tiêu đề “Tổng φ trên các ước”Nhóm các số từ 1 đến n theo ƯCLN của chúng với n. Các số có ƯCLN(k, n) = g có dạng k = g × t với ƯCLN(t, n / g) = 1, nên có đúng φ(n / g) số. Mỗi số thuộc đúng một nhóm, vậy:
Tổng φ(d) trên mọi ước d của n bằng n.
Ví dụ n = 12: φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12.
Cách nhóm theo ƯCLN này giải được nhiều bài tính tổng, ví dụ tổng ƯCLN(k, n) với k từ 1 đến n bằng tổng g × φ(n / g) trên các ước g của n.
Định lý Euler
Phần tiêu đề “Định lý Euler”Nếu ƯCLN(a, m) = 1 thì aφ(m) ≡ 1 (mod m).
Khi m là số nguyên tố, φ(m) = m - 1 và đây chính là định lý Fermat nhỏ. Hệ quả: số mũ có thể lấy dư cho φ(m):
ab ≡ ab mod φ(m) (mod m) khi ƯCLN(a, m) = 1.
Ví dụ 3123 mod 10: φ(10) = 4, 123 mod 4 = 3, nên 3123 ≡ 33 = 27 ≡ 7. Chữ số tận cùng của 3123 là 7.
Nếu b cho dưới dạng xâu rất dài (105 chữ số), tính b mod φ(m) bằng cách đọc từng chữ số: r = (r × 10 + chữ số) mod φ(m).
Định lý Euler mở rộng
Phần tiêu đề “Định lý Euler mở rộng”Khi a và m không nguyên tố cùng nhau, công thức trên sai. Ví dụ 2100 mod 12 = 4, nhưng 100 mod φ(12) = 100 mod 4 = 0 cho 20 = 1.
Lý do: dãy lũy thừa 2, 4, 8, 4, 8, 4, … theo modulo 12 có một đoạn chưa lặp ở đầu (số 2), rồi mới lặp lại. Định lý mở rộng cho phép “nhảy qua” đoạn đầu đó:
Với mọi a, nếu b ≥ φ(m) thì ab ≡ a(b mod φ(m)) + φ(m) (mod m).
Với 2100 mod 12: số mũ thành 0 + 4 = 4, 24 = 16 ≡ 4. Đúng.
Khi b nhỏ hơn φ(m) thì tính trực tiếp. Phải biết b có nhỏ hơn φ(m) hay không, nên với số mũ cho bằng công thức (bc, n!, tháp lũy thừa) cần theo dõi thêm “giá trị thật đã vượt φ(m) chưa”.
Tháp lũy thừa aaa… mod m: áp dụng định lý mở rộng nhiều lần, với modulo m, φ(m), φ(φ(m)), … Dãy này giảm về 1 rất nhanh (φ(m) chẵn với m ≥ 3 và φ của số chẵn không quá một nửa số đó), nên chỉ cần khoảng 2 × log2(m) tầng.
Bậc của một số
Phần tiêu đề “Bậc của một số”Theo định lý Euler, khi ƯCLN(a, m) = 1 luôn có k để ak ≡ 1 (mod m). Số k nhỏ nhất như vậy gọi là bậc của a theo modulo m, và bậc luôn là ước của φ(m).
Tìm bậc: bắt đầu k = φ(m), với mỗi ước nguyên tố q của φ(m), chừng nào k chia hết cho q và ak / q ≡ 1 thì chia k cho q.
Ví dụ: bậc của 10 theo modulo 7 là 6, nên 1/7 = 0,(142857) có chu kỳ 6 chữ số. Bậc của 10 theo modulo n chính là độ dài chu kỳ của phân số 1/n (khi n không chia hết cho 2 và 5).
Luyện tập
Phần tiêu đề “Luyện tập”Gồm 21 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.
Nhóm 1. Tính hàm Euler
Phần tiêu đề “Nhóm 1. Tính hàm Euler”Bài 1. Con ếch trên vòng tròn
Phần tiêu đề “Bài 1. Con ếch trên vòng tròn”Có n ô xếp thành vòng tròn, đánh số 0 đến n - 1. Con ếch đứng ở ô 0, mỗi lần nhảy k ô theo chiều kim đồng hồ. Nhập n (1 ≤ n ≤ 1012). In ra số giá trị k từ 1 đến n mà con ếch nhảy mãi sẽ đi qua tất cả các ô.
Ví dụ: nhập 6 thì in ra 2.
Kiểm tra: nhập 999999999999.
Bài 2. Nhiều câu hỏi φ
Phần tiêu đề “Bài 2. Nhiều câu hỏi φ”Dòng đầu là Q (Q ≤ 105), dòng sau có Q số x1, …, xQ (1 ≤ xi ≤ 106). In ra φ(xi) của từng số trên một dòng, cách nhau bởi dấu cách.
Ví dụ:
| Nhập | In ra |
|---|---|
51 2 6 10 12 | 1 1 2 4 4 |
Kiểm tra: nhập
61000000 999983 720720 65536 362880 999999Bài 3. Cặp số nguyên tố cùng nhau
Phần tiêu đề “Bài 3. Cặp số nguyên tố cùng nhau”Nhập N (1 ≤ N ≤ 106). In ra số cặp có thứ tự (x, y) với 1 ≤ x, y ≤ N và ƯCLN(x, y) = 1.
Ví dụ: nhập 3 thì in ra 7.
Kiểm tra: nhập 1000000.
Bài 4. Đếm số có ƯCLN cho trước
Phần tiêu đề “Bài 4. Đếm số có ƯCLN cho trước”Nhập n và g (1 ≤ g ≤ n ≤ 1012). In ra số các số k từ 1 đến n sao cho ƯCLN(k, n) = g.
Ví dụ: nhập 12 2 thì in ra 2.
Kiểm tra: nhập 1000000000000 1000.
Bài 5. Tổng các ƯCLN
Phần tiêu đề “Bài 5. Tổng các ƯCLN”Nhập n (1 ≤ n ≤ 1012). In ra ƯCLN(1, n) + ƯCLN(2, n) + … + ƯCLN(n, n).
Ví dụ: nhập 6 thì in ra 15.
Kiểm tra: nhập 1000000000000.
Nhóm 2. Định lý Euler và số mũ khổng lồ
Phần tiêu đề “Nhóm 2. Định lý Euler và số mũ khổng lồ”Bài 6. Số mũ có 100000 chữ số
Phần tiêu đề “Bài 6. Số mũ có 100000 chữ số”Dòng đầu có a và m (1 ≤ a, m ≤ 109, ƯCLN(a, m) = 1). Dòng thứ hai là số mũ b, có thể dài tới 105 chữ số. In ra ab mod m.
Ví dụ:
| Nhập | In ra |
|---|---|
3 10123 | 7 |
Kiểm tra: nhập
123456789 10000000009999999999999999999999999999999999999999Bài 7. Khi a và m không nguyên tố cùng nhau
Phần tiêu đề “Bài 7. Khi a và m không nguyên tố cùng nhau”Như bài 6 (b dài tới 105 chữ số, 1 ≤ a, m ≤ 109) nhưng không có điều kiện ƯCLN(a, m) = 1. In ra ab mod m.
Ví dụ:
| Nhập | In ra |
|---|---|
2 12100 | 4 |
Kiểm tra: nhập
6 10000000007777777777777777777777777777777777777777Bài 8. Chu kỳ của phân số 1/n
Phần tiêu đề “Bài 8. Chu kỳ của phân số 1/n”Nhập n (3 ≤ n ≤ 1012, n không chia hết cho 2 và 5). Viết 1/n dưới dạng số thập phân vô hạn tuần hoàn. In ra độ dài chu kỳ (số chữ số lặp lại).
Ví dụ: nhập 7 thì in ra 6.
Kiểm tra: nhập 999999999989.
Bài 9. Số toàn chữ số 1
Phần tiêu đề “Bài 9. Số toàn chữ số 1”Nhập n (1 ≤ n ≤ 109, n không chia hết cho 2 và 5). In ra số chữ số của số nhỏ nhất chỉ gồm các chữ số 1 (1, 11, 111, …) chia hết cho n.
Ví dụ: nhập 3 thì in ra 3.
Kiểm tra: nhập 999999937.
Bài 10. Tháp lũy thừa của 2
Phần tiêu đề “Bài 10. Tháp lũy thừa của 2”Tháp k tầng là 22…2 (k số 2), tháp 0 tầng bằng 1. Ví dụ tháp 3 tầng là 24 = 16. Nhập k và m (0 ≤ k ≤ 106, 1 ≤ m ≤ 109). In ra tháp k tầng mod m.
Ví dụ: nhập 3 100 thì in ra 16.
Kiểm tra: nhập 1000000 1000000000.
Nhóm 3. Sàng φ và phân số tối giản
Phần tiêu đề “Nhóm 3. Sàng φ và phân số tối giản”Bài 11. Tổng ƯCLN của mọi cặp
Phần tiêu đề “Bài 11. Tổng ƯCLN của mọi cặp”Nhập N (1 ≤ N ≤ 106). In ra tổng ƯCLN(i, j) với mọi i, j từ 1 đến N (cặp có thứ tự, kể cả i = j).
Ví dụ: nhập 3 thì in ra 12.
Kiểm tra: nhập 1000000.
Bài 12. Đếm phân số tối giản
Phần tiêu đề “Bài 12. Đếm phân số tối giản”Dòng đầu là Q (Q ≤ 105), dòng sau có Q số N1, …, NQ (1 ≤ Ni ≤ 106). Với mỗi N, đếm số phân số tối giản a / b với 0 nhỏ hơn a nhỏ hơn b ≤ N. In ra các đáp số trên một dòng.
Ví dụ:
| Nhập | In ra |
|---|---|
32 3 5 | 1 3 9 |
Kiểm tra: nhập
41000000 999999 1 100Bài 13. ƯCLN là số nguyên tố
Phần tiêu đề “Bài 13. ƯCLN là số nguyên tố”Nhập N (1 ≤ N ≤ 106). Đếm số cặp (i, j) với 1 ≤ i nhỏ hơn j ≤ N mà ƯCLN(i, j) là một số nguyên tố.
Ví dụ: nhập 6 thì in ra 4.
Kiểm tra: nhập 1000000.
Bài 14. Tổng các BCNN
Phần tiêu đề “Bài 14. Tổng các BCNN”Nhập n (1 ≤ n ≤ 1012). In ra BCNN(1, n) + BCNN(2, n) + … + BCNN(n, n), lấy dư cho 109 + 7.
Ví dụ: nhập 4 thì in ra 24.
Kiểm tra: nhập 1000000000000.
Bài 15. Ngôi sao đều
Phần tiêu đề “Bài 15. Ngôi sao đều”Đặt n điểm cách đều trên một đường tròn. Chọn số bước k (2 ≤ k nhỏ hơn n / 2), xuất phát từ một điểm, cứ nối điểm hiện tại với điểm cách nó k bước, cho tới khi quay về chỗ cũ. Nếu đường gấp khúc đi qua cả n điểm thì ta được một ngôi sao đều. Nhập n (3 ≤ n ≤ 1012). In ra số ngôi sao đều khác nhau (số giá trị k thỏa mãn).
Ví dụ: nhập 5 thì in ra 1.
Kiểm tra: nhập 999999999999.
Nhóm 4. Vận dụng
Phần tiêu đề “Nhóm 4. Vận dụng”Bài 16. Lũy thừa hai tầng
Phần tiêu đề “Bài 16. Lũy thừa hai tầng”Nhập a, b, c, m (0 ≤ a ≤ 1018, 0 ≤ b ≤ 1018, 1 ≤ c ≤ 1018, 1 ≤ m ≤ 109). In ra a(bc) mod m (quy ước 00 = 1).
Ví dụ: nhập 2 3 2 1000 thì in ra 512.
Kiểm tra: nhập 123456789123456789 987654321987654321 1000000000000000000 1000000000.
Bài 17. Áp dụng φ liên tiếp
Phần tiêu đề “Bài 17. Áp dụng φ liên tiếp”Nhập n (1 ≤ n ≤ 1012). Thay n bằng φ(n), lặp lại cho tới khi n = 1. In ra số lần thay.
Ví dụ: nhập 10 thì in ra 3.
Kiểm tra: nhập 999999999989.
Bài 18. Tổng các số nguyên tố cùng nhau với n
Phần tiêu đề “Bài 18. Tổng các số nguyên tố cùng nhau với n”Nhập n (1 ≤ n ≤ 1012). In ra tổng các số k từ 1 đến n với ƯCLN(k, n) = 1, lấy dư cho 109 + 7.
Ví dụ: nhập 10 thì in ra 20.
Kiểm tra: nhập 999999999989.
Bài 19. Phân số nhỏ hơn một nửa
Phần tiêu đề “Bài 19. Phân số nhỏ hơn một nửa”Nhập N (1 ≤ N ≤ 106). Đếm số phân số tối giản a / b với a, b nguyên dương, b ≤ N và a / b nhỏ hơn 1/2.
Ví dụ: nhập 5 thì in ra 4.
Kiểm tra: nhập 1000000.
Bài 20. Lũy thừa giai thừa
Phần tiêu đề “Bài 20. Lũy thừa giai thừa”Nhập a, n, m (0 ≤ a ≤ 1018, 0 ≤ n ≤ 106, 1 ≤ m ≤ 109). In ra an! mod m.
Ví dụ: nhập 2 3 100 thì in ra 64.
Kiểm tra: nhập 6 1000000 1000000000.
Bài 21. Nguyên tố cùng nhau trên đoạn rất dài
Phần tiêu đề “Bài 21. Nguyên tố cùng nhau trên đoạn rất dài”Nhập N và n (1 ≤ N ≤ 1018, 1 ≤ n ≤ 1012). Đếm số các số k từ 1 đến N với ƯCLN(k, n) = 1.
Ví dụ: nhập 20 6 thì in ra 7.
Kiểm tra: nhập 1000000000000000000 999999999990.
© 2026 Bumbii Academy. Toàn bộ nội dung thuộc bản quyền của Bumbii Academy, nghiêm cấm sao chép dưới mọi hình thức khi chưa được cho phép.