e603 - 10104 - Euclid Problem
題目描述
題目要求對於給定的兩個正整數 A 和 B，找到整數 X 和 Y 使得 AX + BY 等於 A 和 B 的最大公因數 D。如果有多個解，則輸出 |X| + |Y| 最小的解，如果有多組滿足最小值，則輸出 X ≤ Y 的解。
解題思路
本題的核心是擴展歐幾里得演算法 (Extended Euclidean Algorithm)。擴展歐幾里得演算法不僅可以求出兩個數的最大公因數 (GCD)，還可以找到滿足 Bezout 等式的整數係數 X 和 Y，即 AX + BY = GCD(A, B)。
程式碼中 extended_euclidean 函數實現了擴展歐幾里得演算法。它使用迭代的方式計算 GCD 以及係數 s 和 t。在迴圈中，它不斷更新 old_r, r, old_s, s, old_t, 和 t，直到 r 變成 0。最後，old_s 和 old_t 就是 Bezout 等式的係數 X 和 Y，old_r 就是 GCD。
主函數 main 讀取輸入的 A 和 B，調用 extended_euclidean 函數計算 X、Y 和 D，然後輸出結果。
複雜度分析
- 時間複雜度: O(log(min(a, b)))，擴展歐幾里得演算法的時間複雜度與輾轉相除法的時間複雜度相同。
- 空間複雜度: O(1)，演算法使用常數級別的額外空間。
程式碼
#include <iostream>
#define ll long long
using namespace std;
//這裡用了int型別，所支持的整數範圍較小，且本程序僅支持非負整數，可能缺乏實際用途，僅供展示。
struct EX_GCD { //s,t是裴蜀等式中的係數，gcd是a,b的最大公因數
ll s,t,gcd;
};
struct EX_GCD extended_euclidean(ll a, ll b) {
struct EX_GCD ex_gcd;
if (b == 0) { //b=0時直接結束求解
ex_gcd.s = 1;
ex_gcd.t = ex_gcd.gcd = 0;
return ex_gcd;
}
ll old_r = a, r = b , old_s = 1, s = 0 , old_t = 0, t = 1;
while (r != 0) { //按擴展歐基里德算法進行循環
ll q = old_r / r;
ll temp = old_r;
old_r = r;
r = temp - q * r;
temp = old_s;
old_s = s;
s = temp - q * s;
temp = old_t;
old_t = t;
t = temp - q * t;
}
ex_gcd.s = old_s;
ex_gcd.t = old_t;
ex_gcd.gcd = old_r;
return ex_gcd;
}
int main() {
cin.tie(0); ios::sync_with_stdio(false);
ll a, b;
while(cin >> a >> b){
struct EX_GCD sol = extended_euclidean(a, b);
cout << sol.s << " " << sol.t << " " << sol.gcd << "\n";
}
return 0;
}