Tác giả:
Reviewer:
Đây là khái niệm tương đối quen thuộc với chúng ta.
Cho hai số tự nhiên và . Số nguyên dương lớn nhất thoả mãn và gọi là ước chung lớn nhất (greatest common divisor - GCD) của và . Kí hiệu là (ƯCLN(a, b) trong tiếng Việt) hoặc đơn giản hơn .
Về mặt toán học, với thì , và không xác định. Tuy nhiên, để lập trình tiện lợi ta quy ước .
Định nghĩa ƯCLN cũng có thể mở rộng cho số nguyên. Khi đó .
Có một vài cách để tìm ƯCLN của hai số và . Cách đơn giản nhất là ... duyệt từng số tự nhiên một đến để kiểm tra điều kiện và . Ngoài ra, trong toán học, ta cũng sử dụng phương pháp phân tích thành thừa số nguyên tố để tìm ƯCLN. Phương pháp này không hiệu quả lắm khi lập trình. Thay vào đó, chúng ta sẽ sử dụng thuật toán Euclid.
Thuật toán này được trình bày trong tác phẩm "Cơ sở" (Elements) của Euclid vào khoảng năm 300 TCN, nhưng cũng có thể đã từng xuất hiện trước đó.
Thuật toán được thực hiện bằng cách liên tục áp dụng công thức sau cho tới khi ra kết quả:
Nếu là ước của và , hiển nhiên nó cũng là ước của .
Nếu là ước của và , hiển nhiên nó cũng là ước của .
Do vậy với ba số , , , nếu một số bất kỳ là ước của một trong ba số trên thì sẽ là ước của hai số còn lại, tức là ƯC(a, b) = ƯC(b, a - b). Điều này dẫn đến .
Phép tính sau khi thực hiện lần thì sẽ thoả mãn . Số sau khi trừ đi lần trở thành .
Vậy (đpcm).
int gcd(int a, int b)
{
if (b == 0) return a;
return gcd(b, a % b);
}
Hoặc ngắn hơn:
int gcd(int a, int b)
{
return (b ? gcd(b, a % b) : a);
}
Định lý Lamé: Thuật toán Euclid cần thực hiện ít hơn lần chia lấy dư.
Thuật toán chạy chậm nhất khi , , với là số Fibonacci thứ . Khi đó thuật toán cần thực hiện lần đệ quy.
So với các phép toán khác, phép lấy phần dư (%) chậm hơn một chút dù vẫn có độ phức tạp là . Chúng ta có thể xây dựng một cách cài đặt khác không sử dụng phép toán này.
Ta có một số tính chất sau:
Kết hợp với ta cài đặt như sau (Code tham khảo từ CP Algorithms):
int gcd(int a, int b)
{
if (!a || !b) return a | b;
int shift = __builtin_ctz(a | b);
a >>= __builtin_ctz(a);
do
{
b >>= __builtin_ctz(b);
if (a > b)
swap(a, b);
b -= a;
} while (b);
return a << shift;
}
Đoạn code trên thực hiện những công việc sau:
__builtin_ctz(k) đếm số bit tận cùng của ).Thuật toán cải tiến trên sẽ thực hiện chia lần trong trường hợp tệ nhất. Do vậy, độ phức tạp của thuật vẫn không đổi và là .
algorithm của C++ có hỗ trợ hàm __gcd(a, b) để tìm ước chung lớn nhất của hai số và , cũng sử dụng thuật Euclid. Kể từ phiên bản C++17, thư viện numeric hỗ trợ thêm hàm gcd(a, b) với mục đích tương tự. Các hàm có sẵn này có thể được sử dụng để code ngắn gọn.Khi tính toán, công thức trên sẽ gây tràn số nếu quá lớn, nhưng ta có thể giải quyết dễ dàng bằng cách thực hiện phép chia trước:
Kể từ C++17, thư viện numeric cũng hỗ trợ cả hàm lcm(a, b) cho phép tính BCNN của hai số.
Với hai số tự nhiên và , thuật toán này được sử dụng để viết dưới dạng tổ hợp tuyến tính. Nói cách khác, thuật toán này sẽ tìm một bộ giá trị nguyên thoả mãn:
Ví dụ:
Các số thoả mãn đẳng thức trên luôn tồn tại theo bổ đề sau:
Bổ đề Bézout: Với hai số nguyên , có ƯCLN là , tồn tại hai số nguyên và thoả mãn . Hơn nữa, tất cả các số nguyên có dạng đều là bội của .
Xét trường hợp . Với quy ước đã nói tới ở trên, mọi giá trị nguyên của đều thoả mãn đẳng thức . Bây giờ ta sẽ giải quyết bài toán với không đồng thời bằng .
Rõ ràng, luôn tồn tại các giá trị để . Gọi là số nguyên dương nhỏ nhất thoả mãn (với là các số nguyên). Ta chứng minh rằng là ƯCLN của và .
Do đó cũng có dạng . Tuy nhiên, số dương nhỏ nhất có dạng như vậy là , thế nhưng nên , đồng nghĩa với .
Chứng minh tương tự ta cũng được . Từ đó suy ra là ước chung của và .
Xét là một ước chung bất kỳ khác của và . Đặt với là số nguyên. Ta có:
Suy ra . Vì dương và khác nên .
Vậy là ƯCLN của và . Bổ đề được chứng minh.
Ứng dụng trực tiếp của thuật toán này là các phương trình Diophantus, sẽ được thảo luận ở phần sau.
Xét bài toán với hai số ban đầu là và . Gọi là ƯCLN của và .
Khi thực hiện thuật toán Euclid (không mở rộng) để tìm , sau khi biến đổi hoàn tất ta thu được . Lúc này ta có , tức là .
Từ các giá trị ở trên, ta truy lại các giá trị ở bước trước và thay đổi các hệ số để đẳng thức đúng trong bước này.
Giả sử tại một bước ta có . Đặt . Ta thấy và .
Lại giả sử trước bước đó sau khi áp dụng thuật toán Euclid mở rộng, ta được bộ và các hệ số là .
Ta cần tìm các hệ số để: .
Liên tục cập nhật các hệ số theo công thức trên tới khi thu được như ban đầu, ta sẽ thu được kết quả.
// Hàm trả về ƯCLN của a và b đồng thời thay đổi giá trị của x, y
int extEuclid(int a, int b, int& x, int& y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
int q = a / b;
int r = a - b * q;
int x1 = 0, y1 = 0;
int d = extEuclid(b, r, x1, y1);
x = y1;
y = x1 - q * y1;
return d;
}
Thuật toán Euclid mở rộng thực tế chỉ là thêm một vài bước tính toán vào thuật toán Euclid thường nên độ phức tạp vẫn là .
Phương trình Diophantus (Diophantine function) tuyến tính hai ẩn có dạng như sau:
Phương trình trên có vô số nghiệm thực (trừ khi , khi đó phương trình vô nghiệm). Tuy nhiên, ta chỉ quan tâm đến các nghiệm nguyên của phương trình.
Để cho ngắn gọn, bài viết sẽ sử dụng cụm từ "phương trình Diophantus" để chỉ phương trình Diophantus tuyến tính hai ẩn.
Bài tập áp dụng trực tiếp: CEQU
Khi , phương trình có nghiệm nếu và vô nghiệm nếu
Khi phương trình có nghiệm nếu và vô nghiệm nếu . Tương tự khi .
Bây giờ ta chỉ xét các trường hợp .
Lưu ý: Phần dưới đây không thực sự liên quan tới thuật toán để giải bài này, đồng thời kết quả cũng khá phức tạp và không phải thứ chúng ta cần lúc này. Bạn đọc cân nhắc trước khi xem.
Từ ta rút ra:
Vế trái và modulo của đồng dư thức trên cùng chia hết cho . Do vậy, . Nếu điều ngược lại xảy ra, phương trình vô nghiệm.
Chia hai vế và modulo của đồng dư thức cho được:
Vì nên tồn tại nghịch đảo modulo của . Nhân hai vế của đồng dư thức với giá trị này được:
Do đó họ các nghiệm của phương trình là:
Ta đã biết phương trình chỉ có nghiệm nếu . Nếu điều kiện này không thoả mãn, ta kết luận phương trình vô nghiệm.
Giả sử là các số dương. Đặt .
Sử dụng thuật toán Euclid mở rộng, ta có:
Nhân hai vế của phương trình với được:
Suy ra phương trình có nghiệm:
Trường hợp không dương, ta thay đổi dấu của để thoả mãn đẳng thức.
Thay nghiệm trở lại phương trình, ta được:
Từ đẳng thức này ta kết luận các nghiệm của phương trình có dạng:
Chốt lại, để tìm nghiệm của một phương trình Diophantus, ta tìm các hệ số từ thuật toán Euclid mở rộng, rồi từ các hệ số này áp dụng vào các công thức trên để tính ra kết quả.
Đoạn chương trình sau tìm một nghiệm nguyên của phương trình , với :
const pair <int, int> INVALID_ROOT = {INT_MAX, INT_MAX};
//Hàm trả về ƯCLN của a và b, biến đổi x, y thoả mãn ax + by = \gcd(a, b)
int extEuclid(int a, int b, int &x, int&y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
int q = a / b;
int r = a - b * q;
int x1 = 0, y1 = 0;
int d = extEuclid(b, r, x1, y1);
x = y1;
y = x1 - q * y1;
return d;
}
//Tìm 1 nghiệm nguyên của phương trình ax + by + c = 0
pair <int, int> diophantineSolve(int a, int b, int c)
{
int x = 0, y = 0;
int d = extEuclid(a, b, x, y);
if (c % d != 0) return INVALID_ROOT;
x *= c / d;
y *= c / d;
if (a < 0) x = -x;
if (b < 0) y = -y;
return make_pair(x, y);
}
Bài tập áp dụng trực tiếp: SGU 106
Tóm tắt đề bài: Đếm số cặp số nguyên thoả mãn:
Các trường hợp có hoặc là tầm thường. Ta chỉ xét và .
Ở phần trước, ta đã có công thức nghiệm tổng quát của các phương trình Diophantus từ một nghiệm bất kỳ:
Dễ thấy các nghiệm của bài toán lúc này chỉ phụ thuộc vào . Bài toán trở thành tìm sao cho và thoả mãn các điều kiện đã cho. Lúc này ta chỉ cần thay ngược biểu thức của và theo vào rồi suy ngược ra là xong.
Nếu bài toán yêu cầu liệt kê chi tiết các nghiệm này, ta cũng chỉ cần tăng lên dần dần trong khoảng thoả mãn.
Bài toán này yêu cầu chúng ta tìm nghiệm có dương nhỏ nhất.
Cộng từng vế của biểu thức nghiệm và theo được:
Dễ thấy nghiệm nhỏ nhất khi nhỏ nhất. Tuỳ thuộc vào dấu của , ta chọn sao cho giá trị của biểu thức là cực tiểu.
Bài tập áp dụng: Euclid Problem. Ở bài này .
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ụ:
Không phải số tự nhiên nào cũng có nghịch đảo modulo; chẳng hạn, không có nghịch đảo modulo của .
Xét phương trình Diophantus . Khi phương trình có nghiệm , ta có:
Ta thấy nghiệm của phương trình là nghịch đảo modulo của . Qua đó ta cũng thấy, nghịch đảo modulo chỉ tồn tại khi và chỉ khi .
Nghịch đảo modulo thường được sử dụng trong những bài toán chia số lớn lấy phần dư, điển hình là các bài toán tính tổ hợp. Chẳng hạn:
(Lưu ý rằng công thức trên chỉ đúng nếu nguyên tố cùng nhau với với mọi thoả mãn dữ liệu của đề)
Khi modulo là số nguyên tố, để tiện lợi ta thường dùng định lý Fermat nhỏ để suy ra rồi dùng luỹ thừa nhanh để tính. Còn nếu không nguyên tố, ta lại áp dụng thuật toán Euclid mở rộng để tìm nghịch đảo modulo qua phương trình .