跳转至

欧几里得算法

欧几里得算法（辗转相除法）可以在 \(O\big(\log \min(a,b)\big)\) 为上界的时间复杂度内求出 \(a,b\) 的最大公约数。

1
2
3
4
int gcd(int a, int b) {
    if(b == 0) return a;
    return gcd(b, a % b);
}

正确性分析

只需证明：\(\forall a,b\)，\((a,b)=(a-b,b)\)。

记 \(d_1=(a,b)\)，\(a=k_1d_1,\ b=k_2d_1\)。容易证明 \(d_1\mid (a-b,b)\)。同理，我们记 \(d_2=(a-b,b)\)，\(a-b=k_3d_2,\ b=k_4d_2\)，因此 \(a=(k_3+k_4)d_2\)，\(d_2\mid (a,b)\)。得证。

时间复杂度分析

我们发现，若 \(a>b\)，则 \(a\bmod b<\frac{a}{2}\)（反证法易证）。

因此，每进行 \(2\) 次取模操作，较大数 \(a\) 至少变为原来的一半。考虑到进行第一次操作后，一定有 \(a',b'\le \min(a,b)\)。因此总操作次数不超过 \(O\big(\log \min(a,b)\big)\)。

进一步的，我们可以证明：求 \(n\) 个数的 \(\gcd\) 的时间复杂度为 \(O(n+\log V)\)。记 \(n\) 个数依次为 \(a_{1},\cdots,a_n\)，前 \(i\) 个数的 \(\gcd\) 为 \(g\)。我们尝试加入第 \(i+1\) 个数，即调用 gcd(g, a[i + 1])。

  • 如果 \(a_{i+1}\le g\)，则本次 gcd(g, a[i + 1]) 产生的时间复杂度都计入辗转相除的势能，均摊 \(O(\log V)\)。
  • 如果 \(a_{i+1}>g\)，考虑 gcd(g[i], a[i + 1]) 执行的第一次取模：\(a'_{i+1}\leftarrow a_{i+1}\bmod g[i]\)，得到的 \(a'_{i+1}<g_i\)，这里总共 \(O(n)\)。现在，我们得到了一个比 \(g\) 小的 \(a'_{i+1}\)，剩余部分的复杂度同上。

贝祖定理

若 \(a,b,x,y\in \Z\)，则 \(\gcd(a,b)=1\) 是 \(ax+by\) 能取到的最小正整数值 \(=1\) 的充要条件。

证明

设 \(ax+by\) 能取到的最小正整数值为 \(S\)，此时 \(x=X\)，\(y=Y\)。

将 \(a\) 对 \(S\) 取模：\(a=qS+r\)，其中 \(r\in[0,S)\)；

将 \(aX+bY=S\) 代入 \(a=qS+r\)：

\[ q(aX+bY)+r=aX+bY \]

解出 \(r\)：

\[ r=aX(1-q)+bY(1-q) \]

我们发现，如果 \(r\neq 0\)，又因为 \(r<S\)，则 \(S\) 不是最小的正整数值。因此 \(r=0\)，这样 \(S\) 一定是 \(a\) 的约数。

同理，\(S\) 一定是 \(b\) 的约数。又因为 \(a,b\) 互质，所以 \(S=1\)，得证。

由贝祖定理，我们可以判断一个二元一次不定方程是否具有整数解。例如：

\[ ax+by=c \]

我们先求出 \(d=\gcd(a,b)\)，然后判断是否满足 \(d\mid c\)，若满足，则存在整数解，否则不存在整数解。

扩展欧几里得算法 exgcd

扩欧算法可以在 \(O(\log)\) 的时间复杂度内求出一个二元一次不定方程的一组整数解（或判定无解情况）。

即，求出一组 \((x,y)\) 满足

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

同时返回 \(d=\gcd(a,b)\)，这样我们就可以根据贝祖定理判定原方程是否有整数解，并求出原方程 \(ax+by=c\) 的一组解 \((x,y)\)。

原理：\(ax+by=d\) 的特解可以由 \((a\bmod b)x+by=d\) 的一组特解得出：

\[ \begin{align*} bx+(a\bmod b)y&=d\\ bx+(a-\lfloor\frac{a}{b}\rfloor b)y&=d\\ ay+b(x-\lfloor\frac{a}{b}\rfloor y)&=d \end{align*} \]
\[ \begin{cases} x=y_1\\ y=x_1-\lfloor\frac{a}{b}\rfloor y_1 \end{cases} \]

代码

1
2
3
4
5
6
7
8
9
void exgcd(const int &a, const int &b, int &x, int &y, int &d) {
    if(b == 0) {
        x = 1, y = 0;
        d = a;
        return;
    }
    exgcd(b, a % b, y, x, d);
    y -= a / b * x;
}

细节问题

使用 exgcd 需要特别注意一些问题：

  • 注意大数相乘会不会溢出 int 或者 long long；
  • 注意传入的 \(a\) 或 \(b\) 若为负数，可能会导致返回的 \(d<0\)，导致后续程序出现问题。