Thuật toán euclid mở rộng
Tác giả: Huỳnh Văn Duy
Có thể nói trong lập trình thống kê giám sát thì những bài toán về số học tập chiếm một trong những phần khá lớn. Trong đó, trong những thuật toán được biết đến nhiều tuyệt nhất là giải mã euclid mở rộng, thuật toán này rất có thể giải quyết không hề ít bài toán tương quan đến số học. Nên bây giờ chúng ta sẽ mày mò về nó.
Bạn đang xem: Thuật toán euclid mở rộng
ĐẦU TIÊN TA CẦN TÌM HIỂU MỘT CHÚT VỀ THUẬT TOÁN EUCLID NGUYÊN THỦY
Lịch sử thuật toán Euclid:
Thuật toán Euclid là trong những thuật toán cổ nhất được biết thêm đến, từ lúc nó xuất hiện trong cuốn Euclid’s Elements khoảng tầm năm 300 trước công nguyên. Euclid mở đầu đã trình bày rõ ràng vấn đề về góc nhìn hình học, như vụ việc tìm ra một thước đo thông thường cho độ dài hai tuyến đường thẳng, và thuật toán của ông đã xử lý bằng cách lặp lại phép trừ đoạn dài hơn cho đoạn ngắn hơn. Mặc dù nhiên, thuật toán đã đa số không được phát hiện tại ra vày Euclid và nó đã có thể được biết đến sớm hơn 200 năm. Nó cũng đã được nghe biết bởi Eudoxus of Cnidus (khoảng năm 375 trước công nguyên) và Aristotle (khoảng năm 330 trước công nguyên).
Mô tả thuật toán:
Cho 2 số tự nhiên và thoải mái a và b, ko đồng thời bằng 0: chất vấn nếu b bởi 0, thì a là mong chung lớn số 1 (UCLN). Giả dụ không, lặp lại xử lý thực hiện b cùng phần còn lại sau thời điểm lấy a phân chia cho b. Phần còn lại sau thời điểm chia a đến b thường xuyên được viết là a mod b.
Các thuật toán này hoàn toàn có thể sử dụng trong bất kì hoàn cảnh nào lúc còn phần dư. Điều này bao gồm các nhóm nhiều thức như đội số nguyên Gauxơ. Thuật toán không những áp dụng đến số tự nhiên và thoải mái mà còn vận dụng cho những trường hợp tổng thể khác sẽ được mô tả chi tiết sau.
Xem thêm: Cô Nàng Bướng Bỉnh - Co Nang Buong Binh Tap 11
Thuật toán có thể được thiết lập rất 1-1 giản:
#include #include using namespace std;#define builtin_gcd __gcdint gcd(int a, int b) if(b==0) return a; else return gcd(b,a%b);int main(){ cout
Dĩ nhiên, ngôn từ lập trình C++ cũng cung ứng cho bọn họ một hàm tất cả sẵn nhằm tìm mong chung lớn số 1 của hai số bởi thuật toán euclid, đó là hàm __gcd(a, b) đang trả về mong chung lớn số 1 của hai số a và b.
THUẬT TOÁN EUCLID MỞ RỘNG
Phương trình diophantine:

Theo định lí Bézout (Bézout’s indentify): đến hai số nguyên a, b lúc đó luôn luôn tồn tại nhị số x, y chang cho:

Người ta cũng chứng tỏ được phương trình trên gồm nghiệm khi và chỉ còn khi gcd(a, b) = c. Và như thế có nghĩa là phương trình diophante rất có thể có rất nhiều nghiệm, cùng từ từng một nghiệm ta hoàn toàn có thể sinh ra đầy đủ nghiệm khác.
Định nghĩa số nguyên k sao cho:




Dễ thấy




Suy ra:






Trong đó:

hay

Như vây, trường hợp


Ví dụ: Tìm tất cả các nghiệm của phương trình

Xem thêm: Bảng Báo Cáo Kết Quả Hoạt Đông Kinh Doanh Của Công Ty, Bảng Báo Cáo Kết Quả Hoạt Động Kinh Doanh
Đầu tiên, ta xét


















Cài đặt cầm thể:
// Extended euclid solve diophantine linear equation#include #define x first#define y secondusing namespace std;typedef long long ll;typedef pair ii;ll a, b, c;ii extended_gcd(ll a, ll b) if (b == 0) return ii(1, 0); ii qr = ii(a / b, a % b); ii st = extended_gcd(b, qr.y); return ii(st.y, st.x - qr.x*st.y);void extended_gcd2(ll a, ll b, ll &X, ll &Y) // another version ll d = __gcd(a, b); ll m = a, n = b; ll xm = 1; // (ym = 0) m = a = a*1 + b*0 ll xn = 0; // (yn = 1) n = a = a*0 + b*1 while (n) ll q = m / n; ll r = m - q*n; ll xr = xm - q*xn; m = n, xm = xn; n = r, xn = xr; X = xm * (c/d); Y = ((d - a*xm) / b) * (c/d);int main() freopen("in.txt", "r", stdin); scanf("%lld %lld %lld", &a, &b, &c); ll d = __gcd(a, b); ii ex = extended_gcd(a, b); printf("%lld %lldn", c/d*ex.x, c/d*ex.y); ll X, Y; extended_gcd2(a, b, X, Y); printf("%lld %lldn", X, Y); assert(c/d*ex.x == X && c/d*ex.y == Y); return 0;NGHỊCH ĐẢO MODULO
Một trong số những ứng dụng đặc trưng nhất của thuật toán Euclid không ngừng mở rộng đó đó là dùng để tìm nghịch hòn đảo modulo:



Ta có:


Khi kia


Ví dụ: a = 7, m = 10, Xét phương trình

Nghiệm

Khi đó:

TỔNG KẾT:
Thuật toán Euclid mở rộng hoàn toàn có thể dùng nhằm giải phương trình Diophantine

BONUS: ĐỊNH LÍ THẶNG DƯ trung hoa (CHINESE REMAINDER THEOREM)
Định lý thặng dư nước trung hoa là tên bạn phương tây đặt mang lại định lý này. Người china gọi nó là việc Hàn Tín điểm binh. Hàn Tín là 1 danh tướng tá thời Hán Sở, từng được phong tước vương thời Hán Cao Tổ giữ Bang đang dựng nghiệp. Sử ký tứ Mã Thiên viết rằng Hàn Tín là tướng mạo trói con gà không nổi, nhưng rất có tài quân sự. Tương truyền rằng khi Hàn Tín điểm quân số, ông mang đến quân bộ đội xếp sản phẩm 3, sản phẩm 5, mặt hàng 7 rồi báo cáo số dư. Từ đó ông tính đúng chuẩn quân số cho từng người.
Gần đây, định lý số dư Trung Quốc có tương đối nhiều ứng dụng trong số bài toán về số nguyên lớn vận dụng vào triết lý mật mã. – Wikipedia
Bản hóa học của câu hỏi Hàn Tín điểm binh là giải phương trình đồng dư nhảy nhất được tế bào tả tổng quát như sau: