AcWing 877. 扩展欧几里得算法（拓展欧几里得模板）

题目链接

https://www.acwing.com/problem/content/879/

思路

由贝祖定理我们可以得到 a x + b y = k ∗ g c d ( a , b ) ax+by=k*gcd(a,b) ax+by=k∗gcd(a,b)一定存在，那么我们通过欧几里得算法进行递归运算，详情请看这边博客： https://acmer.blog.csdn.net/article/details/122280910

代码

#include
using namespace std;
#define ll long long

ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x = 1,y = 0;
        return a;
    }
    ll d = exgcd(b,a%b,y,x);
    y -= a/b * x;
    return d;
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n--){
        ll a,b,x,y;
        scanf("%lld %lld",&a,&b);
        exgcd(a,b,x,y);
        printf("%lld %lld\n",x,y);
    }
    
    return 0;
}