C++基础：扩展欧几里得算法

裴蜀定理

内容：有一对正整数a、b，那么一定存在非0整数x、y，使得 ax+by=(a,b)

扩展欧几里得算法

用于求ax+by=(a,b)中的一个特解x,y

补充：此时y=y-floor(a/b)*x

 

#include

#include

using namespace std;

int exgcd(int a,int b,int &x,int &y){

    if (b==0){

        x=1,y=0;

        return a;

    }

    int d=exgcd(b,a%b,y,x);

    y-=a/b*x;

    return d;

}

int main(){

    int n;

    scanf("%d",&n);

    while (n--){

        int a,b,x,y;

        scanf("%d%d",&a,&b);

        exgcd(a,b,x,y);

        printf("%d %d\n",x,y);

    }

    return 0;

}