扩展欧几里得算法——例题4（最大公约数问题2）数论

最大公约数问题2 题目描述输入正整数A，B，C，求一组X, Y,使得方程：AX+BY=C，保证有解。
输出任何一组解即可。
输入第1行：1个整数T，表示测试数据的组数 (1 <= T <= 100)
接下来T行，每行2个整数，表示A和B和C (1 <= A, B <= 1000， 1 <= C <= 10^9)
输出输出T行，每行2个整数，表示X和Y
样例输入

1 14 8 4

样例输出

-2 4

解析这和最大公约数问题1有相同之处。我们先求出 AX + BY = GCD(A,B)的整数解X,Y。

∵ AX + BY = GCD(A,B)
【扩展欧几里得算法——例题4（最大公约数问题2）】∴ A(CX) + B(CY) = GCD(A,B) * C
∴ A(XC / GCD(A,B)) + B(YC / GCD(A,B)) = C

若有整数解的话，就必须满足 C / GCD(A,B) 也是整数，即 C mod GCD(A,B) = 0，题目保证有解，就不管了，直接除。

#include #include #include #include using namespace std; int read() { int f = 1,x = 0; char s = getchar(); while(s < '0' || s > '9') {if(s == '-')f = -1; s = getchar(); } while(s >= '0' && s <= '9') {x = x * 10 + s - '0'; s = getchar(); } return x * f; } bool f[2005]; int p[2005]; int n,m,i,j,k,s,o,num,num1; int exgcd(int a,int b,int &x,int &y) { if(!b) { x = 1,y = 0; return a; } else { int r = exgcd(b,a % b,y,x); y -= x * (a / b); return r; } } void answer(int a,int b,int c,int &x,int &y) { int cu = c / exgcd(a,b,x,y); x *= cu; y *= cu; } int main() { n = read(); while(n --) { s = read(); o = read(); k = read(); answer(s,o,k,i,j); printf("%d %d\n",i,j); } return 0; }