extendedeuclid.cpp
Bài toán
Từ thuật toán Euclid (tìm GCD), ta biết được rằng tồn tại cặp số (x, y) sao cho ax+by=GCD(a, b). Hãy xác định một cặp số (x, y).
Độ phức tạp
trường hợp xấu nhất : 5 * log10(min(a, b)) (theo Wikipedia, hay 17 * log2(min(a, b)) )
(xảy ra khi a, b là hai số Fibonacci liên tiếp)
Code này của : Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <algorithm>
using namespace std;
#define long long long
typedef pair<long, long> ii;
typedef pair<long, ii> triple;
#define X first
#define Y second
ii extended_gcd(long a, long b) {
ii qr, st;
if (b == 0)
return ii(1, 0);
else {
qr = ii(a / b, a % b);
st = extended_gcd(b, qr.Y);
return ii(st.Y, st.X - qr.X * st.Y);
}
}
long gcd(long a, long b) {
if (a == 0)
return b;
else
return gcd(b % a, a);
}
int main() {
for (;;) {
int p, q;
if (scanf("%lld%lld", &p, &q) < 0) return 0;
ii ww = extended_gcd(p, q);
printf("%lld %lld %lld\n", ww.X, ww.Y, gcd(p, q));
}
}
Nhận xét
Bằng thuật toán Euclid mở rộng này, ta sẽ tìm được cặp số (x, y) thỏa mãn |x|+|y| là nhỏ nhất, nếu có nhiều cặp (x, y) như vậy, thuật toán này sẽ đưa ra (x, y) thỏa mãn x<=y. (theo uVA)
Giả mã
function extended_gcd(a, b)
if b == 0
return (1, 0)
else
(q, r) := divide (a, b)
(s, t) := extended_gcd(b, r)
return (t, s - q * t)
(theo Wikipedia)
Tham khảo