题目描述

扩展欧几里得算法求系数
求 $x$ , $y$ 使得 $x*a+y*b == (a,b)$
递归求解，$a_{i},b_{i} ,x_{i},y_{i}$ 为第i次递归的 $a,b,x,y$ 值。
则有
$$x_{i}*a_{i}+y_{i}*b_{i} == x_{i+1}*a_{i+1}+y_{i+1}*b_{i+1}$$
其中 $a_{i+1}==b_{i}，b_{i+1}==a_{i} \bmod b_{i} $
因此有
$$\begin{array}{l} x_{i}*a_{i}+y_{i}*b_{i} == x_{i+1}*b_{i}+y_{i+1}*(a_{i} \bmod b_{i})\\ x_{i}*a_{i}+y_{i}*b_{i} == x_{i+1}*b_{i}+y_{i+1}*[a_{i}-(a_{i} // b_{i})*b_{i} ]\\ x_{i}*a_{i}+y_{i}*b_{i} == y_{i+1}*a_{i}+(x_{i+1}-y_{i+1}*(a_{i}//b_{i}))*b_{i} \end{array} $$
得可以有
$$\begin{array}{l} \left\{\begin{matrix} x_{i} = y_{i+1}\\ y_{i} = x_{i+1}-y_{i+1}*(a_{i}//b_{i}) \end{matrix}\right. \end{array} $$

样例

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int exgcd(int max,int min,int &x,int &y){//即使前小后大，经过一轮转换，也能交换过来，之后的都是前小后大，不妨令前大后小。
    if(min==0){
        x=1;y=0;
        return max;
    }
    exgcd(min,max%min,x,y);
    int c = y;
    y = x - max/min*y;
    x = c;
}
int main(){
    int N;
    int a,b,g;
    int x,y;
    cin>>N;
    while(N--){
        cin>> a>> b;
        g = exgcd(a,b,x,y);
        cout<<x<<' '<<y<<'\n';

    }
}