扩展欧几里得

#include<iostream>
using namespace std;

// 裴蜀定理: 对于任意正整数a, b，一定存在整数x, y, 使得ax + by = gcd(a, b)
// 同时gcd(a, b)也是a b能凑出来的最小正整数

// 扩展欧几里得算法 求出 x y
int exgcd(int a, int b, int &x, int &y){
    if(b){
        int d = exgcd(b, a % b, y, x);
        // gcd(b, a mod b) = gcd(a, b) = y * b + x * (a - b * a / b)
        y -= a / b * x;
        return d;
    }
    else{
        x = 1;
        y = 0;
        return a;
    }
}

int main(){
    int a, b;
    cin >> a >> b;
    int x, y;
    exgcd(a, b, x, y);
    cout << x << " " << y;
    return 0;
}