Tổ hợp modulo số nguyên tố nhỏ: Legendre, Kummer, Lucas
Bài Lũy thừa nhanh tính C(n, k) mod p bằng công thức gt[n] × nghịch đảo(gt[k]) × nghịch đảo(gt[n - k]). Cách đó chỉ đúng khi n nhỏ hơn p: nếu n lớn hơn hoặc bằng p thì gt[n] chia hết cho p, mẫu số cũng có thể chia hết cho p, và không có nghịch đảo nào cả. Với p nhỏ (2, 3, 13, 10007) và n đến 1018, cần ba công cụ khác:
- Công thức Legendre: n! chia hết cho p bao nhiêu lần.
- Định lý Kummer: C(n, k) chia hết cho p bao nhiêu lần, đọc từ phép cộng trong cơ số p.
- Định lý Lucas: C(n, k) mod p bằng tích các tổ hợp của từng chữ số trong cơ số p.
Các bạn cần nắm vững bài Lũy thừa nhanh (Fermat nhỏ, nghịch đảo) và bài Định lý số dư Trung Hoa trước khi học bài này.
Công thức Legendre
Phần tiêu đề “Công thức Legendre”Số mũ của số nguyên tố p trong n! là
e = n // p + n // p2 + n // p3 + …
Lý do: trong các số từ 1 đến n, có n // p số chia hết cho p, mỗi số góp ít nhất một thừa số p. Có n // p2 số chia hết cho p2, mỗi số góp thêm một thừa số nữa, và cứ thế.
Ví dụ 10! với p = 2: 10 // 2 + 10 // 4 + 10 // 8 = 5 + 2 + 1 = 8. Thật vậy 10! = 3628800 = 28 × 14175.
def legendre(n, p): """Số mũ của p trong n!""" s = 0 while n: n //= p s += n return s
print(legendre(10, 2)) # 8print(legendre(100, 5)) # 24: 100! có 24 chữ số 0 tận cùng#include <iostream>using namespace std;
// Số mũ của p trong n!long long legendre(long long n, long long p) { long long s = 0; while (n) { n /= p; s += n; } return s;}
int main() { cout << legendre(10, 2) << endl; // 8 cout << legendre(100, 5) << endl; // 24 return 0;}Chia chính n cho p ở mỗi bước (thay vì tính pi) nên không bao giờ bị tràn số. Số bước khoảng logp(n).
Từ đó, số mũ của p trong C(n, k) = n! / (k! × (n - k)!) là
legendre(n, p) - legendre(k, p) - legendre(n - k, p).
Với p không nguyên tố (ví dụ cơ số 12 = 22 × 3), phân tích ra thừa số nguyên tố, tính cho từng thừa số rồi lấy giá trị nhỏ nhất của (số mũ trong n!) // (số mũ trong cơ số).
Định lý Kummer
Phần tiêu đề “Định lý Kummer”Số mũ của p trong C(a + b, a) bằng số lần nhớ khi đặt tính cộng a + b trong cơ số p.
Ví dụ C(10, 3) = 120 = 23 × 15. Cộng 3 + 7 trong cơ số 2:
0 0 1 1 (3) + 0 1 1 1 (7) --------- 1 0 1 0 (10)Nhớ ở bit 0, bit 1, bit 2: đúng 3 lần.
Hệ quả rất hay dùng: cộng n + n trong cơ số 2 thì mỗi bit 1 của n nhớ đúng một lần, nên số mũ của 2 trong C(2n, n) bằng số bit 1 của n.
Định lý Lucas
Phần tiêu đề “Định lý Lucas”Viết n và k trong cơ số p: n = (nm … n1 n0), k = (km … k1 k0). Khi đó
C(n, k) ≡ C(nm, km) × … × C(n1, k1) × C(n0, k0) (mod p)
với quy ước C(a, b) = 0 khi b lớn hơn a.
Ví dụ C(10, 3) mod 3: 10 = 101 và 3 = 010 trong cơ số 3. Tích là C(1, 0) × C(0, 1) × C(1, 0) = 1 × 0 × 1 = 0, nên C(10, 3) chia hết cho 3 (thật vậy, 120 = 3 × 40).
Ví dụ C(10, 3) mod 7: 10 = 13 và 3 = 03 trong cơ số 7. Tích là C(1, 0) × C(3, 3) = 1. Thật vậy 120 = 7 × 17 + 1.
Mỗi chữ số đều nhỏ hơn p, nên chỉ cần bảng giai thừa từ 0 đến p - 1, và tổ hợp nhỏ tính bằng nghịch đảo theo Fermat nhỏ như bình thường.
def tao_bang(p): gt = [1] * p for i in range(1, p): gt[i] = gt[i - 1] * i % p return gt
def c_nho(n, k, p, gt): """C(n, k) % p với n, k nhỏ hơn p""" if k > n: return 0 return gt[n] * pow(gt[k] * gt[n - k], p - 2, p) % p
def lucas(n, k, p, gt): kq = 1 while n or k: kq = kq * c_nho(n % p, k % p, p, gt) % p if kq == 0: return 0 n //= p k //= p return kq
gt7 = tao_bang(7)print(lucas(10, 3, 7, gt7)) # 1print(lucas(10 ** 18, 12345, 7, gt7))#include <iostream>#include <vector>using namespace std;
long long luyThua(long long a, long long b, long long m) { long long kq = 1; a %= m; while (b) { if (b & 1) kq = kq * a % m; a = a * a % m; b >>= 1; } return kq;}
vector<long long> taoBang(long long p) { vector<long long> gt(p, 1); for (long long i = 1; i < p; i++) gt[i] = gt[i - 1] * i % p; return gt;}
// C(n, k) % p với n, k nhỏ hơn plong long cNho(long long n, long long k, long long p, const vector<long long> >) { if (k > n) return 0; return gt[n] * luyThua(gt[k] * gt[n - k] % p, p - 2, p) % p;}
long long lucas(long long n, long long k, long long p, const vector<long long> >) { long long kq = 1; while (n || k) { kq = kq * cNho(n % p, k % p, p, gt) % p; if (kq == 0) return 0; n /= p; k /= p; } return kq;}
int main() { vector<long long> gt7 = taoBang(7); cout << lucas(10, 3, 7, gt7) << endl; // 1 cout << lucas(1000000000000000000LL, 12345, 7, gt7) << endl; return 0;}Tạo bảng mất p bước, mỗi lần gọi lucas mất khoảng logp(n) bước. Lucas hợp với p
nhỏ (đến khoảng 106, để bảng vừa bộ nhớ). Khi p lớn hơn n, chỉ có một chữ số và Lucas
trở về công thức giai thừa thông thường.
Lưu ý: định lý Lucas chỉ đúng khi p là số nguyên tố. Với “cơ số 6”: C(6, 3) = 20 ≡ 2 (mod 6), nhưng tích theo chữ số cơ số 6 là C(1, 0) × C(0, 3) = 0, sai.
Trường hợp p = 2: tam giác Sierpinski
Phần tiêu đề “Trường hợp p = 2: tam giác Sierpinski”Với p = 2, mỗi chữ số là một bit, và C(0, 1) = 0 là trường hợp duy nhất bằng 0. Vậy:
C(n, k) lẻ khi và chỉ khi mọi bit 1 của k cũng là bit 1 của n, tức (n & k) == k.
Kéo theo hàng n của tam giác Pascal có đúng 2(số bit 1 của n) số lẻ. Tô màu các số lẻ của tam giác Pascal, ta được hình tam giác Sierpinski: 2m hàng đầu có đúng 3m số lẻ.
hàng 0: 1hàng 1: 1 1hàng 2: 1 . 1hàng 3: 1 1 1 1hàng 4: 1 . . . 1hàng 5: 1 1 . . 1 1hàng 6: 1 . 1 . 1 . 1hàng 7: 1 1 1 1 1 1 1 1(dấu chấm là số chẵn). Ví dụ hàng 6 = 110 có 2 bit 1, nên có 4 số lẻ.
Modulo là tích các số nguyên tố khác nhau
Phần tiêu đề “Modulo là tích các số nguyên tố khác nhau”Khi modulo m = p1 × p2 × … (các số nguyên tố khác nhau), tính C(n, k) mod pi bằng Lucas cho từng pi, rồi ghép lại bằng định lý số dư Trung Hoa.
Ví dụ C(10, 3) = 120 theo modulo 1001 = 7 × 11 × 13: các số dư là 1, 10, 3, ghép lại được đúng 120.
Nếu m chia hết cho p2 (ví dụ m = 4, 9, 109) thì Lucas không đủ, cần các kỹ thuật khó hơn (định lý Granville). Trong đề thi, modulo thường được chọn là số nguyên tố lớn (109 + 7) hoặc số nguyên tố nhỏ, hoặc tích các số nguyên tố khác nhau như ở đây.
Luyện tập
Phần tiêu đề “Luyện tập”Gồm 20 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. Công thức Legendre
Phần tiêu đề “Nhóm 1. Công thức Legendre”Bài 1. Số mũ của p trong n!
Phần tiêu đề “Bài 1. Số mũ của p trong n!”Nhập n và số nguyên tố p (1 ≤ n ≤ 1018, 2 ≤ p ≤ 1018). In ra số mũ lớn nhất e sao cho n! chia hết cho pe.
Ví dụ: nhập 10 2 thì in ra 8.
Kiểm tra: nhập 1000000000000000000 7.
Bài 2. Số chữ số 0 tận cùng trong cơ số b
Phần tiêu đề “Bài 2. Số chữ số 0 tận cùng trong cơ số b”Nhập n và b (1 ≤ n ≤ 1018, 2 ≤ b ≤ 1012). Viết n! trong hệ cơ số b. In ra số chữ số 0 ở tận cùng.
Ví dụ: nhập 10 12 thì in ra 4.
Kiểm tra: nhập 1000000000000000000 1000000000000.
Bài 3. Giai thừa nhỏ nhất chia hết cho m
Phần tiêu đề “Bài 3. Giai thừa nhỏ nhất chia hết cho m”Nhập m (1 ≤ m ≤ 1012). In ra số nguyên dương n nhỏ nhất sao cho n! chia hết cho m.
Ví dụ: nhập 12 thì in ra 4.
Kiểm tra: nhập 999999999999.
Bài 4. Tích các giai thừa
Phần tiêu đề “Bài 4. Tích các giai thừa”Nhập n và số nguyên tố p (1 ≤ n ≤ 109, 2 ≤ p ≤ 109). In ra số mũ của p trong tích 1! × 2! × 3! × … × n!.
Ví dụ: nhập 5 2 thì in ra 8.
Kiểm tra: nhập 1000000000 2.
Bài 5. Số mũ của p trong C(n, k)
Phần tiêu đề “Bài 5. Số mũ của p trong C(n, k)”Nhập n, k và số nguyên tố p (0 ≤ k ≤ n ≤ 1018, 2 ≤ p ≤ 1018). In ra số mũ lớn nhất e sao cho C(n, k) chia hết cho pe.
Ví dụ: nhập 10 3 2 thì in ra 3.
Kiểm tra: nhập 1000000000000000000 123456789012345678 3.
Nhóm 2. Định lý Kummer, chẵn lẻ của tổ hợp
Phần tiêu đề “Nhóm 2. Định lý Kummer, chẵn lẻ của tổ hợp”Bài 6. Số lần nhớ khi cộng
Phần tiêu đề “Bài 6. Số lần nhớ khi cộng”Nhập a, b và số nguyên tố p (0 ≤ a, b ≤ 1018, 2 ≤ p ≤ 109). Đặt tính cộng a + b trong hệ cơ số p. In ra số lần phải nhớ.
Ví dụ: nhập 7 5 2 thì in ra 3.
Kiểm tra: nhập 123456789123456789 987654321987654321 10.
Bài 7. Chẵn hay lẻ
Phần tiêu đề “Bài 7. Chẵn hay lẻ”Dòng đầu là T (T ≤ 105), T dòng sau mỗi dòng có n, k (0 ≤ k ≤ n ≤ 1018). Với mỗi dòng in ra LE nếu C(n, k) lẻ, CHAN nếu chẵn.
Ví dụ:
| Nhập | In ra |
|---|---|
44 25 17 36 3 | CHANLELECHAN |
Kiểm tra: nhập
31000000000000000000 01000000000000000000 11152921504606846975 123456789Bài 8. Số lẻ trên một hàng tam giác Pascal
Phần tiêu đề “Bài 8. Số lẻ trên một hàng tam giác Pascal”Nhập n (0 ≤ n ≤ 1018). Hàng n của tam giác Pascal gồm C(n, 0), C(n, 1), …, C(n, n). In ra số các số lẻ trên hàng đó.
Ví dụ: nhập 6 thì in ra 4.
Kiểm tra: nhập 1000000000000000000.
Bài 9. Bao nhiêu số không chia hết cho p
Phần tiêu đề “Bài 9. Bao nhiêu số không chia hết cho p”Nhập n và số nguyên tố p (0 ≤ n ≤ 1018, 2 ≤ p ≤ 109). In ra số các số k từ 0 đến n sao cho C(n, k) không chia hết cho p.
Ví dụ: nhập 10 3 thì in ra 4.
Kiểm tra: nhập 1000000000000000000 7.
Bài 10. Số Catalan lẻ
Phần tiêu đề “Bài 10. Số Catalan lẻ”Số Catalan thứ n là Cn = C(2n, n) / (n + 1). Dòng đầu là T (T ≤ 105), T dòng sau mỗi dòng một số n (0 ≤ n ≤ 1018). Với mỗi n in ra LE nếu Cn lẻ, CHAN nếu chẵn.
Ví dụ:
| Nhập | In ra |
|---|---|
501237 | LELECHANLELE |
Kiểm tra: nhập
410000000000000000001152921504606846975576460752303423487576460752303423488Nhóm 3. Định lý Lucas
Phần tiêu đề “Nhóm 3. Định lý Lucas”Bài 11. C(n, k) modulo p nhỏ
Phần tiêu đề “Bài 11. C(n, k) modulo p nhỏ”Nhập n, k và số nguyên tố p (0 ≤ n, k ≤ 1018, 2 ≤ p ≤ 105). In ra C(n, k) mod p (quy ước C(n, k) = 0 khi k lớn hơn n).
Ví dụ: nhập 10 3 7 thì in ra 1.
Kiểm tra: nhập 999730024299270 123456789012345 99991.
Bài 12. Nhiều câu hỏi
Phần tiêu đề “Bài 12. Nhiều câu hỏi”Dòng đầu có số nguyên tố p và Q (2 ≤ p ≤ 106, Q ≤ 105). Q dòng sau mỗi dòng có n, k (0 ≤ k ≤ n ≤ 1018). Với mỗi dòng in ra C(n, k) mod p.
Ví dụ:
| Nhập | In ra |
|---|---|
5 310 37 225 5 | 010 |
Kiểm tra: nhập
999983 31000000000000000000 11000000000000000000 999999999999999982 499991Bài 13. Rô-bốt trên lưới khổng lồ
Phần tiêu đề “Bài 13. Rô-bốt trên lưới khổng lồ”Rô-bốt đi từ ô (0, 0) đến ô (a, b), mỗi bước sang phải hoặc lên trên một ô. Nhập a, b (0 ≤ a, b ≤ 1017). In ra số đường đi khác nhau, lấy dư cho 13.
Ví dụ: nhập 2 2 thì in ra 6.
Kiểm tra: nhập 12345678901234567 38840214112856189.
Bài 14. Chia kẹo, modulo 10007
Phần tiêu đề “Bài 14. Chia kẹo, modulo 10007”Chia n viên kẹo giống nhau cho k em (1 ≤ k, 0 ≤ n, n + k ≤ 1018), em nào cũng có thể không được viên nào. In ra số cách chia, lấy dư cho 10007.
Ví dụ: nhập 4 3 thì in ra 15.
Kiểm tra: nhập 10028029290265611 123456790.
Bài 15. Hàng tam giác Pascal modulo 3
Phần tiêu đề “Bài 15. Hàng tam giác Pascal modulo 3”Nhập n (0 ≤ n ≤ 1018). Trên hàng n của tam giác Pascal, đếm số các số chia 3 dư 1 và số các số chia 3 dư 2. In ra hai số đó.
Ví dụ: nhập 5 thì in ra 4 2.
Kiểm tra: nhập 1000000000000000000.
Nhóm 4. Modulo hợp số và đếm trên tam giác Pascal
Phần tiêu đề “Nhóm 4. Modulo hợp số và đếm trên tam giác Pascal”Bài 16. C(n, k) modulo 6
Phần tiêu đề “Bài 16. C(n, k) modulo 6”Nhập n, k (0 ≤ k ≤ n ≤ 1018). In ra C(n, k) mod 6.
Ví dụ: nhập 10 3 thì in ra 0.
Kiểm tra: nhập 1152921504606846975 123456789.
Bài 17. Modulo là tích các số nguyên tố khác nhau
Phần tiêu đề “Bài 17. Modulo là tích các số nguyên tố khác nhau”Nhập n, k, m (0 ≤ k ≤ n ≤ 1018, 2 ≤ m ≤ 109). Biết m là tích của các số nguyên tố khác nhau, mỗi số không quá 105. In ra C(n, k) mod m.
Ví dụ: nhập 10 3 1001 thì in ra 120.
Kiểm tra: nhập 1000000000000000000 123456789012 997210243.
Bài 18. Đếm số lẻ trong cả tam giác Pascal
Phần tiêu đề “Bài 18. Đếm số lẻ trong cả tam giác Pascal”Nhập N (1 ≤ N ≤ 1018). Đếm số cặp (n, k) với 0 ≤ k ≤ n nhỏ hơn N mà C(n, k) lẻ, tức số các số lẻ trên N hàng đầu của tam giác Pascal. In ra kết quả mod 109 + 7.
Ví dụ: nhập 4 thì in ra 9.
Kiểm tra: nhập 1000000000000000000.
Bài 19. Đếm số chia hết cho p trong tam giác Pascal
Phần tiêu đề “Bài 19. Đếm số chia hết cho p trong tam giác Pascal”Nhập N và số nguyên tố p (1 ≤ N ≤ 1018, 2 ≤ p ≤ 109). Đếm số cặp (n, k) với 0 ≤ k ≤ n nhỏ hơn N mà C(n, k) chia hết cho p. In ra kết quả mod 109 + 7.
Ví dụ: nhập 10 3 thì in ra 17.
Kiểm tra: nhập 1000000000000000000 7.
Bài 20. Lũy thừa lớn nhất của m chia hết C(n, k)
Phần tiêu đề “Bài 20. Lũy thừa lớn nhất của m chia hết C(n, k)”Nhập n, k, m (0 ≤ k ≤ n ≤ 1018, 2 ≤ m ≤ 1012). In ra số mũ lớn nhất e sao cho C(n, k) chia hết cho me. Ví dụ với m = 10, đó là số chữ số 0 tận cùng của C(n, k).
Ví dụ: nhập 100 50 10 thì in ra 0.
Kiểm tra: nhập 1000000000000000000 500000000000000001 1000000000000.
© 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.