扩展欧几里得算法

需求：求 \(ax + by = gcd(a, b)\) 的一组可行解。

• 设 \(ax_1 + by_1 = gcd(a, b)\)
• 设 \(bx_2 + (a\ \%\ b)y_2 = gcd(b, a\ \%\ b)\)
• 因为 \(gcd(b, a\ \%\ b) = gcd(a, b)\)，所以有：

  \(ax_1 + by_1 = bx_2 + (a\ \%\ b)y_2\)

• 因为 \(a\ \%\ b = a - ⌊\frac{a}{b}⌋b\)，所以：

  \(ax_1 + by_1 = bx_2 + (a\ \%\ b)y_2 = bx_2 + (a - ⌊\frac{a}{b}⌋b)y_2\)

  \(ax_1 + by_1 = ay_2 + bx_2 - ⌊\frac{a}{b}⌋by_2\)

  \(ax_1 + by_1 = ay_2 + b(x_2 - ⌊\frac{a}{b}⌋y_2)\)

• 由于 \(a = a，b = b\)，所以:

  \(x_1 = y_2,\ y_1 = x_2 - ⌊\frac{a}{b}⌋y_2\)

上面的公式其实是一条向下递推公式，要求 \(x_1, y_1\)，就要先求 \(x_2, y_2\)，要求 \(x_2, y_2\)，就要先求 \(x_3, y_3\)，··· 依此类推。

若考虑递推的底部是：

\(1 \cdot gcd(a, b) + s \cdot 0 = gcd(a, b)\)

底部的上面一层是：

\((k + 1)gcd(a, b) + (-k)gcd(a, b) = gcd(a, b)\)

若要满足：\(x_1 = y_2,\ y_1 = x_2 - ⌊\frac{a}{b}⌋y_2\)，则：

\((k + 1) = s,\ -k = 1 - ⌊\frac{(k + 1)gcd(a, b)}{(-k)gcd(a, b)}⌋s\)

\((k + 1) = s,\ -k = 1 + s\)

\(s = (k + 1) = -(k + 1)\)

解得：k = -1, s = 0

我们可以借助求 \(gcd(a, b)\) 的求法到达递推的底部：

typedef long long LL;

LL gcd(LL a, LL b)
{
    if (!a || !b) return a | b;
    return a > b ? gcd(b, a % b) : gcd(a, b % a);
}

到达 \(gcd(a, b)\) 的底部时，为 0 端的 \(y = 0\)，非 0 端的 \(x = 1\)，递归回溯，再确定上面一层：

// 向下递推的过程保证 a > b
LL exgcd(LL a, LL b, LL &x1, LL &y1)
{
    if (!b)
    {
        x1 = 1; y1 = 0; return a;
    }
    LL x2, y2, gd;
    gd = exgcd(b, a % b, x2, y2);
    x1 = y2; y1 = x2 - a / b * y2;
    return gd;
}

有了这个之后，如果我们要求 \(ax + by = c\) 的一对整数解，由于 \(d\ |\ a, d\ |\ b\) 所以 \(d\ |\ (ax + by)\)，即：

\(d\ |\ c\)

我们不妨先求 \(ax + by = gcd(a, b)\) 的一对整数解，然后对该方程左右同时乘上 \(c / gcd(a, b)\) 就可以转换成方程：

\(ac / gcd(a, b)x + bc / gcd(a, b)y = c\)

\(aX + bY = c\) 的解为：\(X = c / gcd(a, b)x，Y = c / gcd(a, b)y\)

如果 \(c / gcd(a, b)\) 不是整数的话，就一定没有整数解，因为上面推导的时候，若有整数解就一定有 \(gcd(a, b)\ |\ c\)，它们的逻辑关系是：

有整数解 \(\rightarrow gcd(a, b)\ |\ c\)

#include <bits/stdc++.h>

using namespace std;
int debuggersum = 0;

// 即使是不成熟的尝试，

typedef long long LL;

// 向下递推的过程保证 a > b
LL exgcd(LL a, LL b, LL &x1, LL &y1)
{
    if (!b)
    {
        x1 = 1; y1 = 0; return a;
    }
    LL x2, y2, gd;
    gd = exgcd(b, a % b, x2, y2);
    x1 = y2; y1 = x2 - a / b * y2;
    return gd;
}

void solve(void)
{
    int n; scanf ("%d", &n);
    while (n --)
    {
        LL a, b; scanf ("%lld%lld", &a, &b);
        LL x, y; 
        if (a >= b)
        {
            exgcd(a, b, x, y);
            printf ("%lld %lld\n", x, y);
        }
        else
        {
            exgcd(b, a, y, x);
            printf ("%lld %lld\n", x, y);
        }
    }
}

// 也胜于胎死腹中的策略。

int main(void)
{
    ifstream fi; ofstream fo;
    fi.open("./lrq.in"); fo.open("./lrq.out");
    if (fi.is_open() && fo.is_open())
    {
        fo << "start running ..." << endl; fo.close(); fi.close();
        for (long long i = 1; i <= 4e8 + 2e7; i++);
        FILE *fin = freopen("./lrq.in", "r", stdin);
        FILE *fout = freopen("./lrq.out", "w", stdout);
        solve(); fclose(fin); fclose(fout);
    }
    else solve();

    return 0;
}