题目描述

https://www.acwing.com/activity/content/problem/content/946/1/

(扩展欧几里得)

翡蜀定理
对于一对正整数$ a, b $, 存在一对非零数 $x, y$, 使得 $ax + by = gcd(a, b)$

易知, 当 $b = 0$时, $x = 1, y = 0$
当 $b ≠ 0$ 时,
由于：$$ gcd(a, b) = gcd(b, a mod b) $$
而 $$ bx’ + (a mod b) * y’ = gcd(b, a mod b) $$
$$ bx’ + (a - ⌊a / b⌋ * b)*y’ = gcd(a, a mod b) $$
$$ ay’ + b * (x’ - ⌊a / b⌋ * y’) = gcd(a, a mod b $$

所以：$ x = y’, y = x’ - ⌊a / b⌋ * y’$
所以只需要递归得到最后一层的$x’, y’$，再回溯计算即可
(稍微说明下，为什么$ a mod b = a - ⌊a / b⌋ * $)
$ a / b = a / b 余 a mod b$(等号后面是结果)
那么 $a - a/b * b = a mod b$

C++ 代码

#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 x1, y1;
    int gcd = exgcd(b, a % b, x1, y1);
    x = y1, y = x1 - (a / b) * y1;
    return gcd;
}

int main()
{
    int n;
    cin >> n;
    while( n --)
    {
        int a, b, x, y;
        cin >> a >> b;
        int gcd = exgcd(a, b, x, y);
        cout << x << ' ' << y << endl;
    }
    return 0;
}