Lũy thừa nhanh
Tính 2 mũ 1018 chia lấy dư cho 109 + 7: nhân từng lần thì cần 1018 phép nhân, ước lượng hơn 300 năm. Lũy thừa nhanh chỉ cần khoảng 60 phép nhân. Đây là công cụ nền tảng cho rất nhiều bài thi học sinh giỏi cấp tỉnh, quốc gia: chia theo modulo, tính tổ hợp, tính số Fibonacci thứ 1018…
Các bạn cần nắm vững bài Đồng dư và phép toán modulo trước khi học bài này.
Ý tưởng: bình phương liên tiếp
Phần tiêu đề “Ý tưởng: bình phương liên tiếp”Để tính 38, không cần nhân 3 tám lần:
32 = 3 × 3, 34 = 32 × 32, 38 = 34 × 34
Chỉ 3 phép nhân. Mỗi lần bình phương thì số mũ gấp đôi.
Với số mũ không phải lũy thừa của 2, ví dụ 13, ta tách 13 thành tổng các lũy thừa của 2: 13 = 8 + 4 + 1 (chính là cách viết 13 trong hệ nhị phân: 1101). Khi đó:
313 = 38 × 34 × 31
Cách làm: vừa bình phương cơ số liên tục (31, 32, 34, 38), vừa xét từng bit của số mũ từ phải sang trái; bit nào bằng 1 thì nhân lũy thừa tương ứng vào kết quả. Chạy tay 313 % 1000:
| Số mũ còn lại | Bit cuối (số mũ % 2) | Cơ số hiện tại | Kết quả |
|---|---|---|---|
| 13 | 1 | 3 (= 31) | 1 × 3 = 3 |
| 6 | 0 | 9 (= 32) | 3 |
| 3 | 1 | 81 (= 34) | 3 × 81 = 243 |
| 1 | 1 | 6561 % 1000 = 561 (= 38) | 243 × 561 % 1000 = 323 |
| 0 | dừng | 323 |
Kiểm tra: 313 = 1594323, ba chữ số cuối là 323.
def luy_thua(a, b, m): kq = 1 % m a %= m while b > 0: if b % 2 == 1: # bit cuối bằng 1: nhân vào kết quả kq = kq * a % m a = a * a % m # bình phương cơ số b //= 2 # bỏ bit cuối return kq
print(luy_thua(3, 13, 1000)) # 323print(luy_thua(2, 10 ** 18, 10 ** 9 + 7)) # 719476260# Python có sẵn: pow(2, 10 ** 18, 10 ** 9 + 7)#include <iostream>using namespace std;
long long luyThua(long long a, long long b, long long m) { long long kq = 1 % m; a %= m; while (b > 0) { if (b % 2 == 1) kq = kq * a % m; // bit cuối bằng 1: nhân vào kết quả a = a * a % m; // bình phương cơ số b /= 2; // bỏ bit cuối } return kq;}
int main() { cout << luyThua(3, 13, 1000) << endl; // 323 cout << luyThua(2, 1000000000000000000LL, 1000000007) << endl; // 719476260 return 0;}Mỗi vòng lặp số mũ giảm một nửa, nên với b = 1018 chỉ có khoảng 60 vòng.
Lưu ý về tràn số: trong C++, a * a an toàn khi m không quá khoảng 3 × 109
(vì a nhỏ hơn m). Nếu m lên tới 1018 thì a * a tràn long long, phải dùng
kiểu __int128 khi nhân (bài 7).
Định lý Fermat nhỏ và phép chia theo modulo
Phần tiêu đề “Định lý Fermat nhỏ và phép chia theo modulo”Bài Đồng dư đã nói: phép chia không có quy tắc modulo đơn giản. Cách giải quyết là thay “chia cho b” bằng “nhân với nghịch đảo của b”: số x sao cho b × x ≡ 1 (mod p).
Ví dụ với p = 7: nghịch đảo của 3 là 5, vì 3 × 5 = 15 ≡ 1 (mod 7). Vậy “chia cho 3” theo modulo 7 chính là “nhân với 5”.
Tìm nghịch đảo thế nào? Định lý Fermat nhỏ: nếu p là số nguyên tố và a không chia hết cho p thì
ap - 1 ≡ 1 (mod p)
Tách ap - 1 = a × ap - 2, ta thấy ngay nghịch đảo của a là ap - 2, tính bằng lũy thừa nhanh. Kiểm tra với p = 7, a = 3: 35 = 243 = 7 × 34 + 5, đúng là 5.
Với p = 109 + 7 (số nguyên tố), nghịch đảo của 2 là 2p - 2 % p = 500000004. Thử lại: 2 × 500000004 = 1000000008 ≡ 1. Đây là lý do đề thi hay chọn modulo là số nguyên tố 109 + 7.
Lưu ý: cách này chỉ dùng được khi modulo là số nguyên tố và số cần chia không chia hết cho modulo.
Tính tổ hợp C(n, k) theo modulo
Phần tiêu đề “Tính tổ hợp C(n, k) theo modulo”Số cách chọn k đồ vật từ n đồ vật là C(n, k) = n! / (k! × (n - k)!). Với n tới 106:
- Tính sẵn
gt[i]= i! % p với mọi i đến n. - Tính nghịch đảo của k! và (n - k)! bằng lũy thừa nhanh.
- C(n, k) = gt[n] × nghịch đảo(gt[k]) × nghịch đảo(gt[n - k]) % p.
Khi có rất nhiều câu hỏi, tính sẵn luôn nghịch đảo của mọi giai thừa (bài 15).
Lũy thừa ma trận
Phần tiêu đề “Lũy thừa ma trận”Lũy thừa nhanh không chỉ dùng cho số mà cho bất kỳ phép nhân nào có tính kết hợp, ví dụ nhân ma trận. Ứng dụng nổi tiếng nhất là tính số Fibonacci thứ n với n tới 1018.
Một bước của dãy Fibonacci biến cặp (F(i + 1), F(i)) thành (F(i + 2), F(i + 1)), với F(i + 2) = F(i + 1) + F(i). Viết dưới dạng nhân ma trận:
- F(i + 2) = 1 × F(i + 1) + 1 × F(i)
- F(i + 1) = 1 × F(i + 1) + 0 × F(i)
Ma trận hệ số (các số in đậm) là A = [[1, 1], [1, 0]]. Làm n bước nghĩa là nhân với An, và tính An bằng lũy thừa nhanh, mỗi phép nhân hai ma trận 2 × 2 là 8 phép nhân số. Người ta chứng minh được An = [[F(n + 1), F(n)], [F(n), F(n - 1)]], nên F(n) nằm ngay ở góc trên bên phải (bài 18).
Mọi dãy dạng “số sau bằng tổng có hệ số của vài số trước” đều làm được theo cách này (bài 20).
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. Lũy thừa nhanh
Phần tiêu đề “Nhóm 1. Lũy thừa nhanh”Bài 1. Lũy thừa modulo
Phần tiêu đề “Bài 1. Lũy thừa modulo”Nhập ba số nguyên dương a, b, m (a, b ≤ 1018, m ≤ 109). In ra ab % m.
Ví dụ: nhập 3 13 1000 thì in ra 323.
Kiểm tra: nhập 2 1000000000000000000 1000000007.
Bài 2. Chữ số tận cùng
Phần tiêu đề “Bài 2. Chữ số tận cùng”Nhập hai số nguyên dương a, b (a, b ≤ 1018). In ra chữ số tận cùng của ab.
Ví dụ: nhập 7 2026 thì in ra 9.
Kiểm tra: nhập 7 1000000000000000000.
Bài 3. Ba chữ số tận cùng
Phần tiêu đề “Bài 3. Ba chữ số tận cùng”Nhập hai số nguyên dương a, b (a, b ≤ 1018). In ra ba chữ số tận cùng của ab (in đủ ba chữ số, ví dụ 024).
Ví dụ: nhập 2 10 thì in ra 024.
Kiểm tra: nhập 2 1000.
Bài 4. Số tập con khác rỗng
Phần tiêu đề “Bài 4. Số tập con khác rỗng”Nhập số nguyên dương n (n ≤ 1018). Một tập có n phần tử có bao nhiêu tập con khác rỗng? In ra kết quả chia lấy dư cho 109 + 7.
Ví dụ: nhập 10 thì in ra 1023.
Kiểm tra: nhập 1000000000000000000.
Bài 5. Tô màu dãy ô
Phần tiêu đề “Bài 5. Tô màu dãy ô”Có n ô xếp thành một hàng và k màu (n ≤ 1018, 2 ≤ k ≤ 109). Tô mỗi ô một màu sao cho hai ô kề nhau luôn khác màu. Có bao nhiêu cách tô? In ra kết quả chia lấy dư cho 109 + 7.
Ví dụ: nhập 4 3 thì in ra 24.
Kiểm tra: nhập 1000000000000000000 3.
Bài 6. Mật khẩu có chữ a
Phần tiêu đề “Bài 6. Mật khẩu có chữ a”Có bao nhiêu xâu độ dài n gồm các chữ cái thường a đến z (26 chữ) có chứa ít nhất một chữ a? Nhập n (n ≤ 1018), in ra kết quả chia lấy dư cho 109 + 7.
Ví dụ: nhập 2 thì in ra 51.
Kiểm tra: nhập 1000000000000000000.
Nhóm 2. Số mũ, modulo rất lớn
Phần tiêu đề “Nhóm 2. Số mũ, modulo rất lớn”Bài 7. Lũy thừa với modulo lớn
Phần tiêu đề “Bài 7. Lũy thừa với modulo lớn”Nhập ba số nguyên dương a, b, m (a, b ≤ 1018, 2 ≤ m ≤ 1018). In ra ab % m.
Ví dụ: nhập 100000000000000000 3 999999999999999999 thì in ra 1000000000000000.
Kiểm tra: nhập 123456789123456789 987654321987654321 999999999999999989.
Bài 8. Số mũ rất lớn
Phần tiêu đề “Bài 8. Số mũ rất lớn”Dòng đầu có hai số nguyên dương a, m (a ≤ 1018, m ≤ 109). Dòng thứ hai là số mũ b, một số nguyên dương có không quá 105 chữ số. In ra ab % m.
Ví dụ:
| Nhập | In ra |
|---|---|
3 10001000 | 1 |
Kiểm tra: nhập
2 1000000007123456789123456789123456789Bài 9. Tổng cấp số nhân
Phần tiêu đề “Bài 9. Tổng cấp số nhân”Nhập ba số nguyên dương a, n, m (a, n ≤ 1018, m ≤ 109, m không nhất thiết là số nguyên tố). In ra (1 + a + a2 + … + an) % m.
Ví dụ: nhập 2 10 1000 thì in ra 47.
Kiểm tra: nhập 3 1000000000000000000 1000000007.
Bài 10. Lũy thừa tầng
Phần tiêu đề “Bài 10. Lũy thừa tầng”Nhập bốn số nguyên dương a, b, c, p (a, b, c ≤ 1018, p ≤ 109 là số nguyên tố, a không chia hết cho p). In ra a(bc) % p.
Ví dụ: nhập 2 3 4 1000000007 thì in ra 993282280.
Kiểm tra: nhập 2 3 1000000000000000000 1000000007.
Nhóm 3. Nghịch đảo modulo và tổ hợp
Phần tiêu đề “Nhóm 3. Nghịch đảo modulo và tổ hợp”Bài 11. Nghịch đảo modulo
Phần tiêu đề “Bài 11. Nghịch đảo modulo”Nhập số nguyên dương a (a ≤ 1018, a không chia hết cho 109 + 7). In ra số x (0 ≤ x nhỏ hơn 109 + 7) sao cho a × x ≡ 1 (mod 109 + 7).
Ví dụ: nhập 3 thì in ra 333333336.
Kiểm tra: nhập 2.
Bài 12. Phân số theo modulo
Phần tiêu đề “Bài 12. Phân số theo modulo”Nhập hai số nguyên dương a, b (a, b ≤ 1018, b không chia hết cho 109 + 7). In ra giá trị của phân số a / b theo modulo 109 + 7, tức là a × (nghịch đảo của b) % (109 + 7).
Ví dụ: nhập 1 3 thì in ra 333333336.
Kiểm tra: nhập 22 7.
Bài 13. Tổng bình phương với n rất lớn
Phần tiêu đề “Bài 13. Tổng bình phương với n rất lớn”Nhập số nguyên dương n (n ≤ 1018). In ra (12 + 22 + … + n2) % (109 + 7).
Ví dụ: nhập 10 thì in ra 385.
Kiểm tra: nhập 1000000000000000000.
Bài 14. Tổ hợp với n lớn
Phần tiêu đề “Bài 14. Tổ hợp với n lớn”Nhập hai số nguyên n, k (0 ≤ k ≤ n ≤ 106). In ra C(n, k), số cách chọn k đồ vật từ n đồ vật, chia lấy dư cho 109 + 7.
Ví dụ: nhập 5 2 thì in ra 10.
Kiểm tra: nhập 1000000 500000.
Bài 15. Nhiều câu hỏi tổ hợp
Phần tiêu đề “Bài 15. Nhiều câu hỏi tổ hợp”Dòng đầu là q (q ≤ 105). Mỗi dòng tiếp theo có hai số n, k (0 ≤ k ≤ n ≤ 106). Với mỗi câu hỏi, in ra C(n, k) % (109 + 7) trên một dòng.
Ví dụ:
| Nhập | In ra |
|---|---|
25 210 3 | 10120 |
Kiểm tra: nhập
35 21000000 50000010 0Bài 16. Số Catalan
Phần tiêu đề “Bài 16. Số Catalan”Số Catalan thứ n là C(2n, n) / (n + 1): số cách viết n cặp ngoặc đúng, ví dụ với n = 3 có 5 cách ((())), (()()), (())(), ()(()), ()()(). Nhập n (n ≤ 106), in ra số Catalan thứ n chia lấy dư cho 109 + 7.
Ví dụ: nhập 3 thì in ra 5.
Kiểm tra: nhập 1000.
Bài 17. Đường đi trên lưới
Phần tiêu đề “Bài 17. Đường đi trên lưới”Một con robot đứng ở góc dưới bên trái của lưới ô vuông, mỗi bước đi sang phải 1 ô hoặc lên trên 1 ô. Có bao nhiêu đường đi để robot đi sang phải đúng m bước và lên trên đúng n bước (m, n ≤ 106)? In ra kết quả chia lấy dư cho 109 + 7.
Ví dụ: nhập 2 2 thì in ra 6.
Kiểm tra: nhập 1000000 1000000.
Nhóm 4. Lũy thừa ma trận
Phần tiêu đề “Nhóm 4. Lũy thừa ma trận”Bài 18. Fibonacci thứ n rất lớn
Phần tiêu đề “Bài 18. Fibonacci thứ n rất lớn”Dãy Fibonacci: F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2). Nhập n (n ≤ 1018), in ra F(n) % (109 + 7).
Ví dụ: nhập 100 thì in ra 687995182.
Kiểm tra: nhập 1000000000000000000.
Bài 19. Xâu nhị phân không có hai số 1 liền nhau
Phần tiêu đề “Bài 19. Xâu nhị phân không có hai số 1 liền nhau”Đếm số xâu nhị phân (chỉ gồm 0 và 1) độ dài n không có hai chữ số 1 đứng liền nhau. Nhập n (1 ≤ n ≤ 1018), in ra kết quả chia lấy dư cho 109 + 7.
Ví dụ: nhập 5 thì in ra 13.
Kiểm tra: nhập 1000000000000000000.
Bài 20. Leo cầu thang rất cao
Phần tiêu đề “Bài 20. Leo cầu thang rất cao”Cầu thang có n bậc, mỗi bước leo 1, 2 hoặc 3 bậc. Nhập n (1 ≤ n ≤ 1018), in ra số cách leo hết cầu thang chia lấy dư cho 109 + 7.
Ví dụ: nhập 4 thì in ra 7.
Kiểm tra: nhập 1000000000000000000.
Bài 21. Tổng cấp số nhân bằng công thức
Phần tiêu đề “Bài 21. Tổng cấp số nhân bằng công thức”Nhập hai số nguyên dương a, n (a, n ≤ 1018, a % (109 + 7) khác 0 và khác 1). In ra (1 + a + a2 + … + an) % (109 + 7).
Ví dụ: nhập 5 10 thì in ra 12207031.
Kiểm tra: nhập 5 1000000000000000000.
© 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.