Code này chưa được kiểm tra.
Bài toán
Xét phương trình ax+by=c (a, b, c > 0). Tìm một cặp nghiệm nguyên (x, y) của phương trình trên. (Phương trình Diophante)
Độ phức tạp
O(log2(min(a, b))) (chi phí tính GCD)
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;
#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);
}
long a, b, c, g;
int main() {
scanf("%lld%lld%lld", &a, &b, &c);
g = gcd(a, b);
ii st = extended_gcd(a, b);
printf("%lld %lld\n", c / g * st.X, c / g * st.Y);
}
Nhận xét
Các bài toán với số học, mình dùng kiểu long long để tránh tràn số.