标签：gcd int 欧几里得 扩展 cfrac 算法 y1 ax aligned

扩展欧几里得算法

问题引入

求 \(ax+by=\gcd(a,b)\) 的一组整数解。

前置知识

欧几里得算法

当 \(a, b\) 为非负整数时，以下等式一定成立。

\[\gcd (a, b) = \gcd (b, a \bmod b) \]

裴蜀定理

对于任意非负整数 \(a, b\) ，一定存在满足的整数对 \((x, y)\) ，使得以下等式成立。

\[ax+by=\gcd(a,b) \]

问题求解

当 \(b=0\) 时，则有 \(ax = a\) ，因而此时有一组解，为 \(x=1,y=0\) 。

当 \(b \neq 0\) 时，由欧几里得算法，可得以下等式。

\[\gcd(a, b) = \gcd(b, a \bmod b) \]

由裴蜀定理，得以下两个等式。

\[\begin{aligned} \gcd(a, b) &= a x + b y \\ \gcd(b, a \bmod b) &= b x_0 + (a \bmod b) y_0 \\ &= b x_0 + (a - \lfloor \cfrac{a}{b} \rfloor b) y_0 \\ &= a y_0 + b(x_0 - \lfloor \cfrac{a}{b} \rfloor y_0) \end{aligned} \]

因为两个等式等价，因此可知 \(x = y_0, y = x_0 - \lfloor \cfrac{a}{b} \rfloor b y_0\) 。

递归算法，最后可以先求得一组特解 \((x', y')\) ，由特解构造通解，得以下式子。

对两个未知数一个加一个数，另一个减去一个数，让这个数达到最小就行。

\[\left\{ \begin{aligned} x &= x' + \cfrac{a}{\gcd(a,b)} * k \\ y &= y’ - \cfrac{a}{\gcd(a,b)} * k \end{aligned} \right. \]

扩展欧几里得算法

扩展欧几里得算法的过程，在上述的问题求解当中，其作用为：求解方程 \(ax + by = \gcd(a, b)\) 的一组特解 \((x_0, y_0)\) 。

具体的实现方式如下。

int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int g, x1, y1;
    g = exgcd(b, a % b, x1, y1);
    x = y1; y = x1 - a / b * y1;
    return g;
}

array<int,3> exgcd(int a, int b) {
    if (b == 0) {
        return {a, 1, 0};
    } else {
        auto [g, x1, y1] = exgcd(b, a % b);
        return {g, y1, x1 - a / b * y1};
    }
}

def exgcd(a : int, b : int):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = exgcd(b, a % b)
    return g, y1, x1 - a // b * y1

不定方程

问题引入

求解 \(ax + by = c\) 的一组整数解。

问题分析

由裴蜀定理可知，对不定方程 \(ax_0 + by_0 = \gcd(a, b)\)，一定有整数解。当 \(\gcd(a, b) \mid c\) 时，一定存在整数解，否则无整数解。因此，我们可以先构建出两个式子。

\[\begin{aligned} ax + by &= c \\ ax_0 + by_0 &= \gcd(a, b) \end{aligned} \]

可以发现，两个式子之间只差了 \(\cfrac{c}{\gcd(a, b)}\) 倍。因此，我们可以先使用扩展欧几里得算法求解 \(ax + by = \gcd(a, b)\) ，再对求出来的解乘上倍数 \(\cfrac{c}{\gcd(a, b)}\) ，我们就得到了方程的一组特解 \((x_0, y_0)\) 。

对于该不定方程，通解的构造也是一样的思路。

\[\left\{ \begin{aligned} x &= x' + \cfrac{a}{\gcd(a,b)} * k \\ y &= y’ - \cfrac{a}{\gcd(a,b)} * k \end{aligned} \right. \]

同余方程

问题引入

给定整数 \(a, b, m\) ，求解同余方程 \(ax \equiv b \pmod m\) 。

如果方程存在整数解，输出任意一个。

问题求解

同余方程可以转化为不定方程的形式。

我们将同余式转化为等式时，可以引入一个新的未知量。

由 \(ax \equiv b \pmod m\) ，可得 \(ax = m(-y) + b\) ，即 \(ax + my = b\) 。

我们只需要使用求解不定方程的方式求解该等式即可。

标签：gcd,int,欧几里得,扩展,cfrac,算法,y1,ax,aligned
From： https://www.cnblogs.com/FlandreScarlet/p/17681368.html