本文共 1214 字，大约阅读时间需要 4 分钟。

最大公约数问题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

样例输入

114 8 4

样例输出

-2 4

解析

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

∵ AX + BY = GCD(A,B)

∴ 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;}
      
     
    
   

转载地址：https://blog.csdn.net/weixin_43960414/article/details/88792106 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！