Tác giả:
Reviewer:
Lớp bài toán liên quan đến số học là một lớp bài toán thường hay xuất hiện trong các kỳ thi học sinh giỏi môn Tin học. Để giải quyết hiệu quả những bài tập này, cần phải nắm vững những kiến thức toán học có liên quan. Bài viết sau đây sẽ cung cấp một số thông tin cơ bản nhất về modulo.
Dưới đây là một số khái niệm cơ bản liên quan đến phép chia
Trong ngôn ngữ C++, phép chia được biểu diễn bằng toán tử /, còn phép lấy dư được biểu diễn bởi toán tử %. Nếu hai toán hạng trong phép tính đều ở kiểu dữ liệu int, kết quả cũng sẽ là kết quả int, do đó a / b là phép lấy thương (hay phần nguyên) của phép chia a cho b, còn a % b là phép lấy phần dư.
Số học modulo hiện đại được nghiên cứu lần đầu bởi C.Gauss năm 1801. Hiện tượng đồng dư cũng thường xuất hiện trong đời sống, chẳng hạn trên chiếc đồng hồ, 15 giờ và 3 giờ cùng được biểu diễn bởi một vị trí kim giờ/phút.
Cho số nguyên . Nếu có hai số nguyên thoả mãn: thì ta nói và đồng dư theo modulo . Ký hiệu là .
Nói cách khác, nếu thì .
Trong ví dụ về đồng hồ nói trên, ta có .
Phép đồng dư có một số tính chất sau đây:
Về mặt cài đặt, đồng dư thức không có nhiều ý nghĩa thiết thực, tuy nhiên nó có vai trò quan trọng trong việc xây dựng lời giải và là nền tảng cho các định lý tiếp sau đây.
Số dư của một phép chia tất nhiên sẽ đồng dư với số bị chia theo modulo là số chia. Vì vậy, mọi tính chất của đồng dư thức đều áp dụng được cho phép toán lấy số dư:
Khi tính hiệu modulo, sẽ xảy ra tình trạng . Để khắc phục, ta cộng thêm một lần vào kết quả để chắc chắn có một số dương (tất nhiên sau đó vẫn lấy mod M):
Với phép luỹ thừa, ta sử dụng luỹ thừa nhị phân thông qua các phép nhân modulo để tính.
Một vấn đề thường gặp phải khi tính toán các bài có modulo là hiện tượng tràn số. Với , dễ thấy khi thì có thể vượt quá giới hạn của int. Vấn đề này có thể được giải quyết một cách đơn giản bằng cách dùng long long; tuy nhiên nếu vẫn muốn sử dụng int để tiết kiệm bộ nhớ, ta có thể sử dụng:
int ans = 1ll * a * b % M
Ngoài ra, ta có thể ép kiểu để trở thành long long bằng cách dùng (long long)a, miễn sao phần tử đầu tiên của phép tính là một số kiểu long long.
Nhìn chung, nên cố gắng thêm % MOD và 1ll * vào mọi phép tính để tránh những sai lầm đáng tiếc.
Bài toán: Tính với là các số nguyên dương và .
Khác với phép cộng, trừ và nhân, dễ thấy không thể có với mọi nguyên. Chẳng hạn, , nhưng đương nhiên không có .
Để giải quyết bài toán này, chúng ta cần một hướng tiếp cận khác. Trong nhiều trường hợp, sẽ là một số nguyên tố, khi đó ta có thể sử dụng phép nghịch đảo modulo để tính kết quả của phép chia.
Nghịch đảo modulo: Số tự nhiên được gọi là nghịch đảo modulo theo modulo của một số tự nhiên nếu . Ký hiệu là .
Ví dụ:
Nghịch đảo modulo của số tự nhiên chỉ tồn tại nếu .
Ta có thể dùng nghịch đảo modulo để tính kết quả của phép chia modulo như sau:
Một cách làm phổ biến để tính nghịch đảo modulo là áp dụng định lý Euler (hoặc định lý Fermat nhỏ), sẽ được trình bày ở dưới đây.
Hàm phi Euler: Đây là khái niệm cốt lõi của định lý Euler.
Hàm phi Euler của số tự nhiên , ký hiệu , là số lượng số tự nhiên nhỏ hơn hoặc bằng mà nguyên tố cùng nhau với
Nếu phân tích được thành thừa số nguyên tố dưới dạng thì ta có thể tính như sau:
Định lý Euler: Nếu và là các số tự nhiên thoả mãn thì ta có
Định lý Fermat nhỏ: Với là số nguyên tố bất kỳ và là số tự nhiên bất kỳ thoả mãn , ta có . Đây là trường hợp đặc biệt của định lý Euler đối với số nguyên tố, khi đó .
Tính nghịch đảo modulo: Để tính nghịch đảo modulo khi là số nguyên tố, ta áp dụng định lý Fermat nhỏ. Do là số nguyên tố, . Do , chia cả hai vế của đồng dư thức trên cho ta được:
Như vậy, là nghịch đảo modulo của . Theo cách này, ta mất thời gian để tìm một nghịch đảo modulo bằng phương pháp luỹ thừa nhị phân.
//Luỹ thừa nhị phân
int binPow(int x, int y, int mod) {
int ret = 0;
for (; y; y /= 2, x = 1ll * x * x % mod) {
if (y % 2) ret = 1ll * ret * x % mod;
}
return ret;
}
//Nghịch đảo modulo
int inv(int x, int mod) {
return binPow(x, mod - 2, mod);
}
//Phép chia modulo
int divMod(int a, int b, int mod) {
return 1ll * a * inv(b) % mod;
}
Chú ý: Kết quả của theo công thức trên vẫn đúng nếu ta thay bằng . Do vậy, ta có thể thực hiện modulo trước khi áp dụng công thức mà không sợ ảnh hưởng đến kết quả.
Trường hợp : Trong trường hợp không phải là số nguyên tố, nếu đã biết ta vẫn có thể tính nghịch đảo modulo bằng cách áp dụng thuật toán Euclid mở rộng để giải phương trình Diophantus . Nghiệm của phương trình trên chính là nghịch đảo modulo của .
Trường hợp : Nghịch đảo modulo chỉ tồn tại nếu , do vậy ta cần dùng một cách khác. Lúc này ta có thể sử dụng công thức:
Giả sử . Khi đó , mà nên . Chia hai vế của đồng dư thức và modulo cho ta được:
Nếu ta chọn thì . Khi đó là số dư trong phép chia cho , còn là số dư trong phép chia cho . Vậy:
//Vẫn là phép chia modulo
int divMod(int a, int b, int mod) {
return a % (1ll * b * mod) / b;
}
Một số lưu ý khi sử dụng công thức trên:
long long nếu là một số rất lớn, do xuất hiện phép nhân .Thông thường, cứ khi nào gặp số to hơn long long, đề bài thường bắt chúng ta lấy kết quả một số nào đó, thường là số nguyên tố.
Bạn đọc có thể tham khảo thêm các phép toán sau:
Thuật toán Euclid mở rộng dùng để tìm các bộ số nguyên sao cho , với là các số nguyên. Áp dụng thuật toán này, ta có thể giải các phương trình Diophantus tuyến tính hai ẩn có dạng (hay ), với là các số nguyên.
Bạn đọc có thể tham khảo chi tiết về thuật toán Euclid mở rộng tại bài viết này.
Định lý: Cho số nguyên dương và sao cho các số nguyên tố cùng nhau đôi một. Hệ phương trình đồng dư (hoặc thặng dư) ẩn :
có họ nghiệm duy nhất là:
trong đó , và là nghịch đảo modulo của .
Chứng minh sự tồn tại: Do là các số đôi một nguyên tố cùng nhau nên dễ thấy , dẫn đến sự tồn tại của . Vì nên
Xét . Ta thấy với mọi thì do là tích của tất cả các với khác . Vì vậy với mọi ta có
Vậy là một nghiệm của hệ phương trình.
Chứng minh sự duy nhất: Giả sử phương trình có hai nghiệm là và . Với mọi , ta đều có . Lấy bội chung nhỏ nhất của tất cả các đồng dư thức dạng trên ta được
Do nên
hay . Nghĩa là, nghiệm theo modulo là duy nhất.
Rất nhiều bài toán đố vui hay dân gian dẫn đến việc phải giải hệ phương trình đồng dư và dẫn đến định lý này, chẳng hạn có bài Hàn Tín điểm binh nổi tiếng. Còn trong lập trình thi đấu, ta không thường xuyên gặp những bài toán với yêu cầu rõ ràng như vậy. Tuy nhiên, định lý này và các kết quả trung gian sử dụng để chứng minh định lý lại là nền tảng để giải rất nhiều bài toán số học, như những bài có tag chinese remainder theorem trên Codeforces.
Định lý thặng dư Trung Hoa cho phép ta nhanh chóng giải một hệ phương trình đồng dư với các modulo đôi một nguyên tố cùng nhau. Chỉ cần tính các và , ta dễ dàng giải được hệ phương trình đồng dư.
Đôi khi, ta gặp phải các bài toán mà trong đó các modulo không nguyên tố cùng nhau với nhau. Trong trường hợp này, ta xét từng cặp phương trình một. Giả sử ta có hệ
Từ hệ này, ta có thể đặt và giải phương trình Diophantus tuyến tính sau bằng thuật toán Euclid mở rộng
Khi đã tìm được và , ta tính hoặc . Nghiệm của hệ sẽ là
Bài rất dễ vận dụng phép chia và đồng dư cơ bản:
Bài cần suy luận nhiều hơn bằng các định lý và kết quả đồng dư: