Tính đồng dư và lũy thừa lớn

Lan thiết kế một vòng quay gồm 12 ô, đánh số từ 0 đến 11. Từ ô 9, bạn ấy tiến 8 bước và muốn biết ô dừng. Một trò chơi khác nhân số trạng thái lên 3 sau mỗi lượt, tới tận một tỷ lượt. Cả hai tình huống đều chỉ cần phần dư, không cần giữ toàn bộ số rất lớn.

Hai số cùng phần dư thuộc cùng một lớp

Vòng quay của Lan có 12 ô. Sau 12 bước, vị trí không đổi; sau 8 bước từ ô 9, bạn đi qua điểm xuất phát rồi tới ô 5.

Phần dư (remainder) của số nguyên a khi chia cho m > 0 là số r thỏa a = q * m + r và 0 <= r < m. Trong Python, a % m cho phần dư đó. Giá trị m được gọi là mô đun (modulus).

Ví dụ này tính ô dừng và so sánh ba số có cùng vị trí trên vòng quay:

print((9 + 8) % 12)
print(5 % 12, 17 % 12, 29 % 12)

5
5 5 5

Các số 5, 17 và 29 cùng có phần dư 5. Chúng thuộc cùng một lớp dư (residue class) theo mô đun 12. Ta viết 17 ≡ 5 (mod 12) vì hiệu 17 - 5 chia hết cho 12.

Hình sau gom các số theo phần dư của chúng. Mỗi hàng là một lớp, không phải một thứ tự duyệt.

Với số âm, Python vẫn giữ phần dư không âm khi mô đun dương. Đẳng thức -3 = (-1) * 12 + 9 cho thấy vì sao phần dư là 9:

a, m = -3, 12
print(a // m, a % m)
print((a // m) * m + a % m)

-1 9
-3

Thương nguyên -1 và phần dư 9 khôi phục đúng -3. Nếu đổi dấu mô đun, quy ước dấu phần dư cũng đổi. Các ví dụ và bài tập sau luôn yêu cầu m > 0.

Mô đun bằng 1 cũng hợp lệ. Chỉ có một phần dư nằm trong khoảng từ 0 đến m - 1, nên mọi số đều cho 0:

print(17 % 1, (-3) % 1, 1 % 1)

0 0 0

Rút gọn sau phép cộng, trừ và nhân vẫn giữ đúng phần dư

Giả sử a = q * m + r và b = t * m + s. Khi cộng, phần chứa q * m và t * m là bội của m. Vì vậy, tổng có cùng phần dư với r + s.

Lập luận tương tự đúng với phép trừ. Với phép nhân, các tích chứa m đều là bội của m. Do đó, với m > 0, ba quy tắc sau luôn đúng:

Đoạn sau so sánh hai cách cho từng phép tính, kể cả hiệu âm:

a, b, m = 10, 18, 7
print((a + b) % m, (a % m + b % m) % m)
print((a - b) % m, (a % m - b % m) % m)
print((a * b) % m, (a % m * (b % m)) % m)

0 0
6 6
5 5

Hai số trên mỗi dòng bằng nhau. Đặc biệt, hiệu 10 - 18 âm nhưng phần dư vẫn nằm trong khoảng từ 0 đến 6. Bạn vẫn cần lấy % m sau phép tính với các phần dư, vì tổng hoặc tích có thể đạt tới m.

Khi nhân nhiều số, ta chỉ cần giữ phần dư hiện tại. Sau mỗi lượt, nó đại diện cho tích của tất cả phần tử đã xét:

m = 11
result = 1 % m
for x in [8, 7, 10, 3]:
    result = result * x % m
    print(x, result)

8 8
7 1
10 10
3 8

Quy tắc nhân đảm bảo thay tích đã xét bằng phần dư của nó không đổi đáp án cuối. Nếu có n số, vòng lặp thực hiện n lượt, nên tốn O(n) phép nhân và dùng O(1) ô nhớ phụ. Với n = 100000, số lượt là 100000; chi phí số nguyên còn phụ thuộc độ lớn các số.

Phép chia không tự động tuân theo ba quy tắc trên. Ví dụ, 6 và 1 cùng dư 1 theo mô đun 5, nhưng chia nguyên cả hai cho 2 cho hai phần dư khác nhau. Ta sẽ xét điều kiện chia ở phần sau.

Một cách kiểm tra quy tắc là thay đầu vào bằng số âm và số lớn hơn mô đun. Chương trình sau đọc hai số và một mô đun, rồi tính biểu thức kết hợp ba phép toán:

-8 13 9

a, b, m = map(int, input().split())
direct = (a * b + a - b) % m
reduced = ((a % m) * (b % m) + a % m - b % m) % m
print(direct, reduced)

1 1

Hai cách cho cùng một phần dư. Ở cách thứ hai, mỗi thành phần được rút gọn trước. Dấu trừ vẫn được giữ nguyên; đổi nó thành dấu cộng sẽ giải một biểu thức khác.

Khi đề chỉ yêu cầu phần dư, bạn có thể rút gọn từng bước mà không đánh mất thông tin cần thiết. Tuy vậy, phần dư không cho biết giá trị ban đầu. Các số 5, 17 và 29 đã chứng minh nhiều giá trị khác nhau cùng có một phần dư.

Vì thế, không thể dùng phần dư để so sánh độ lớn của hai số ban đầu. Chẳng hạn, 11 lớn hơn 8, nhưng phần dư của 11 theo 10 nhỏ hơn phần dư của 8. Nếu đề hỏi số nào lớn hơn, bạn phải giữ thông tin cần thiết khác.

Một ví dụ ứng dụng là cập nhật tổng điểm theo vòng. Lan nhận lần lượt 8, 9 và -4 điểm trên bảng gồm 10 vị trí. Điểm âm nghĩa là lùi trên vòng, không có nghĩa là kết quả cuối âm:

position = 0
for change in [8, 9, -4]:
    position = (position + change) % 10
    print(change, position)

8 8
9 7
-4 3

Sau hai lần đầu, tổng điểm thực là 17 và vị trí là 7. Lần cuối giảm 4, nên vị trí còn 3. Nếu lưu tổng thực, bạn cũng nhận vị trí 3 sau khi lấy phần dư; ở đây chỉ vị trí được yêu cầu.

Chia đôi số mũ giúp giảm số lần tính

Một hệ thống tăng số trạng thái gấp 3 sau mỗi lượt. Sau b lượt, số trạng thái là 3**b. Nếu chỉ cần phần dư theo m, ta không cần tạo số nguyên đầy đủ.

Nhân cơ số b lần mất O(b) phép nhân. Với b = 10**9, đó là một tỷ lượt. Thay vào đó, lũy thừa nhị phân (binary exponentiation) chia đôi số mũ ở mỗi vòng.

Khi b chẵn, a**b = (a*a)**(b//2). Khi b lẻ, giữ thêm một thừa số a, rồi áp dụng quy tắc chẵn cho phần còn lại. Ta lấy phần dư sau mỗi phép nhân.

Với b = 13, các số mũ lần lượt là 13, 6, 3 và 1. Mỗi số lẻ báo rằng lũy thừa hiện tại cần được nhân vào kết quả. Sơ đồ sau thể hiện các bước trên:

Bảng dưới đây do chương trình sinh, tính 3**13 theo mô đun 100. Các cột ghi trạng thái đầu mỗi vòng. Cột bit là phần dư của số mũ khi chia 2.

Ở vòng đầu, b lẻ nên nhân 3 vào kết quả. Vòng sau có b = 6 chẵn, nên chưa nhân thêm. Hai vòng cuối cùng lấy tiếp các thừa số tương ứng với 3**4 và 3**8.

Tại đầu mỗi vòng, result * a**b cùng phần dư với lũy thừa ban đầu. Đây là bất biến vòng lặp (loop invariant). Nếu b chẵn, thay a bằng bình phương và b bằng một nửa không đổi tích đó. Nếu b lẻ, nhân thêm a vào result trước khi chia đôi cũng giữ nguyên tích.

Khi b về 0, a**b bằng 1, nên result là phần dư cần tìm. Nhờ bất biến, kết quả đúng cho mọi b >= 0 và m > 0. Quy ước tính toán trong bài là 0**0 == 1, giống Python.

Chương trình hoàn chỉnh đọc ba số a, b, m và in phần dư:

3 13 100

def mod_power(a, b, m):
    result = 1 % m
    a %= m
    while b > 0:
        if b % 2 == 1:
            result = result * a % m
        a = a * a % m
        b //= 2
    return result

a, b, m = map(int, input().split())
print(mod_power(a, b, m))

23

Số 13 có biểu diễn nhị phân 1101, tức 8 + 4 + 1. Thuật toán chọn ba lũy thừa tương ứng rồi nhân theo mô đun. Kết quả không phụ thuộc vào việc tạo số 3**13 trước.

Với b > 0, số vòng bằng số bit của b, tức floor(log2(b)) + 1. Tại b = 10**18, chỉ cần 60 vòng. Số phép nhân là O(log(b + 1)), bộ nhớ phụ là O(1) số nguyên; phép toán trên số lớn còn phụ thuộc kích thước mô đun.

Nếu b = 0, vòng lặp không chạy. Khởi tạo 1 % m đảm bảo kết quả đúng cả khi m = 1. Cơ số âm cũng được đưa về phần dư không âm trước khi bắt đầu.

Để nhìn rõ vai trò của các bit, ta có thể liệt kê từng mức bình phương. Với cơ số 3, số mũ 13 chọn các mức 1, 4 và 8. Mức 2 không được chọn vì bit tương ứng của 13 bằng 0:

a, exponent, m = 3, 13, 100
power = a % m
weight = 1
while weight <= exponent:
    chosen = (exponent // weight) % 2
    print(weight, power, chosen)
    power = power * power % m
    weight *= 2

1 3 1
2 9 0
4 81 1
8 61 1

Mỗi lần tăng weight gấp đôi, power trở thành bình phương của giá trị trước. Cột cuối bằng 1 tại những mức cần nhân vào kết quả. Đây là cách khác để đọc cùng một thuật toán, không phải một công thức mới.

Số phép nhân không hoàn toàn bằng số vòng. Mỗi vòng có một phép bình phương; vòng có bit 1 thêm một phép nhân vào kết quả. Với số mũ 13, bốn vòng có ba bit 1, nên mã trên thực hiện bảy phép nhân theo mô đun.

Độ phức tạp O(log(b + 1)) đếm số phép nhân, không coi mọi số nguyên lớn là tốn đúng cùng thời gian. Trong các bài có mô đun nhỏ hơn một tỷ, giá trị sau mỗi phép lấy dư nhỏ hơn một tỷ. Vì vậy mỗi tích trung gian, trước khi lấy dư, chỉ cỡ 10**18.

Hãy thử đối chiếu thuật toán tự viết với cách nhân lặp trên các số mũ nhỏ. Hai cách độc lập giúp phát hiện lỗi thứ tự cập nhật hoặc quên xử lý số mũ 0:

def fast(a, b, m):
    result = 1 % m
    a %= m
    while b:
        if b % 2:
            result = result * a % m
        a = a * a % m
        b //= 2
    return result

for b in range(6):
    slow = 1 % 7
    for _ in range(b):
        slow = slow * (-3) % 7
    print(b, fast(-3, b, 7), slow)

0 1 1
1 4 4
2 2 2
3 1 1
4 4 4
5 2 2

Mỗi dòng chứa số mũ, kết quả chia đôi và kết quả nhân lặp. Hai cột kết quả trùng nhau ở từng dòng. Kiểm tra một vài đầu vào không thay thế chứng minh, nhưng rất hữu ích khi tìm lỗi cài đặt.

Hàm pow ba đối số tính trực tiếp phần dư

Python cung cấp pow(a, b, m) cho lũy thừa theo mô đun. Với số nguyên, b >= 0 và m > 0, kết quả bằng a**b % m. Hàm tính phần dư hiệu quả mà không cần dựng toàn bộ lũy thừa khổng lồ.

Đoạn sau thử cơ số âm, số mũ 0 và mô đun 1:

print(pow(-3, 5, 7))
print(pow(0, 0, 9))
print(pow(7, 0, 1))
print(pow(2, 10**18, 1000))

2
1
0
376

Hai đối số pow(a, b) tạo giá trị lũy thừa đầy đủ. Vì thế, pow(a, b) % m không có cùng lợi thế về bộ nhớ với pow(a, b, m). Toán tử ^ cũng không thay cho **: trong Python, nó là phép XOR trên bit.

print(2 ^ 3)
print(2 ** 3)

1
8

Giá trị hai dòng khác nhau vì hai toán tử thực hiện hai phép toán khác nhau. Nếu đề cho nhiều truy vấn độc lập, gọi pow(a, b, m) cho từng dòng. Không nên giảm b theo m - 1 nếu chưa kiểm tra điều kiện của định lý liên quan.

Chia theo mô đun cần nghịch đảo tồn tại

Phép chia thông thường có thể tạo số thực, trong khi bài toán yêu cầu một lớp dư nguyên. Ta cần nghịch đảo nhân (multiplicative inverse) của b theo m: số x sao cho b * x % m == 1.

Ví dụ, theo mô đun 7, số 3 có nghịch đảo là 5 vì 3 * 5 % 7 == 1. Để chia 4 cho 3 theo mô đun này, nhân 4 với 5 rồi lấy phần dư:

m, numerator, denominator = 7, 4, 3
inverse = pow(denominator, m - 2, m)
answer = numerator * inverse % m
print(inverse, answer)
print(denominator * answer % m, numerator % m)

5 6
4 4

Hai giá trị ở dòng cuối bằng nhau, xác nhận nghiệm của phép chia. Theo định lý Fermat nhỏ (Fermat's little theorem), nếu p nguyên tố và b % p != 0, thì b**(p-1) % p == 1. Do đó pow(b, p - 2, p) là nghịch đảo của b.

Điều kiện số nguyên tố rất quan trọng cho công thức này. Nghịch đảo nói chung tồn tại khi gcd(b, m) == 1 với m > 1. Mô đun hợp số vẫn có thể có nghịch đảo, nhưng công thức b**(m-2) không được bảo đảm.

Điều kiện nguyên tố cùng nhau nói rằng ước chung lớn nhất của b và m bằng 1. Xem Bài 6 để ôn cách tính ước chung lớn nhất. Nếu có ước chung lớn hơn 1, mọi tích b*x đều chia hết cho ước đó. Do đó, tích không thể đồng dư với 1 theo m.

Khi nghịch đảo tồn tại, nghiệm của b*x ≡ a (mod m) là duy nhất trong các số từ 0 đến m - 1. Thật vậy, nhân hai vế với nghịch đảo cho x ≡ a*inverse (mod m). Mọi nghiệm khác chỉ chênh nhau một bội của m.

Không nên nhầm điều kiện tồn tại nghịch đảo với điều kiện tồn tại một nghiệm bất kỳ. Với 4*x ≡ 0 (mod 8), nhiều giá trị x thỏa mãn. Tuy nhiên, 4 không có nghịch đảo theo 8, nên không thể chia hai vế bằng 4 như phép chia số thực.

Đoạn sau kiểm tra từng phần dư có thể làm nghiệm. Nó chỉ dùng mô đun nhỏ để minh họa, không phải cách tìm nghịch đảo hiệu quả khi mô đun lớn:

m = 8
solutions = [x for x in range(m) if 4 * x % m == 0]
inverses = [x for x in range(m) if 4 * x % m == 1]
print(solutions)
print(inverses)

[0, 2, 4, 6]
[]

Danh sách nghiệm của phương trình thứ nhất không rỗng. Danh sách nghịch đảo lại rỗng. Với m lên tới một tỷ, duyệt mọi ứng viên có thể cần một tỷ lượt; công thức Fermat cho phép dùng lũy thừa nhanh khi đủ điều kiện.

Khi p nguyên tố và b % p != 0, bạn có thể tự kiểm tra nghịch đảo bằng phép nhân. Cách này hữu ích để rà soát giá trị ở ví dụ nhỏ:

p = 11
for b in [2, 3, 7, 10]:
    inverse = pow(b, p - 2, p)
    print(b, inverse, b * inverse % p)

2 6 1
3 4 1
7 8 1
10 10 1

Cột cuối đều bằng 1. Công thức không áp dụng cho b = 11, vì số đó dư 0 theo 11. Không có số nào nhân với 0 lại cho phần dư 1.

Đoạn sau kiểm tra cả hai khả năng với mô đun 8. Khi không có nghịch đảo, không được kết luận bằng cách chia thông thường:

from math import gcd

for b in [3, 4]:
    if gcd(b, 8) == 1:
        print(b, pow(b, -1, 8))
    else:
        print(b, "khong co nghich dao")

3 3
4 khong co nghich dao

Với b = 4, mọi tích 4*x đều chẵn nên không thể dư 1 theo mô đun 8. Với b = 3, hàm pow dùng số mũ -1 để tính nghịch đảo khi điều kiện nguyên tố cùng nhau được thỏa. Phép gọi với số không có nghịch đảo gây lỗi:

print(pow(4, -1, 8))

ValueError: base is not invertible for the given modulus

Trước khi áp dụng công thức Fermat, hãy kiểm tra mô đun nguyên tố và mẫu không chia hết cho mô đun. Bài 9 sẽ xử lý nhiều phép tính tổ hợp với tiền tính; ở đây bạn chỉ cần kiểm tra một phép chia.

Lỗi thường gặp

Tóm tắt

• Hai số cùng phần dư theo m có hiệu chia hết cho m.
• Có thể rút gọn trước và sau phép cộng, trừ, nhân với m > 0.
• Lũy thừa nhị phân giữ bất biến và giảm số mũ một nửa mỗi vòng.
• pow(a, b, m) tính trực tiếp phần dư của lũy thừa.
• Phép chia theo mô đun cần nghịch đảo; công thức Fermat có điều kiện riêng.

Kiểm tra nhanh

Đọc thêm

• Python: hàm pow mô tả ba đối số và số mũ âm.
• Python: toán tử số học mô tả phép chia lấy dư.
• CP-Algorithms: lũy thừa nhị phân giải thích phép chia đôi số mũ.