扩展欧几里得.md

#裴蜀定理

定理内容简述为：对任意两个正整数a,b，存在x,y令：ax+by=d。其中d必定为gcd（a,b）的整数倍。（x,y是整数，可能其中有一个是负数）

定理证明：裴蜀定理 - 维基百科，自由的百科全书 (wikipedia.org)

#扩展欧几里得

#include <iostream>
#include <algorithm>

using namespace std;

int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        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;
        scanf("%d%d", &a, &b);
        int x, y;
        exgcd(a, b, x, y);
        printf("%d %d\n", x, y);
    }

    return 0;
}