Skip to content

GCD & LCM

最大公约数

GCD ，即 Greatest Common Divisor .

一组整数的最大公约数就是指这组整数的最大的公共约数 .

怎么全是废话

那么要如何求解一组整数的 gcd 捏？

我们先考虑两个数 \(a,b\) 的情况 .

令 \(a=bq+r(q,r\in\mathbb{N})\) ，则 \(a \bmod b=r\in[0,b)\) ，假设 \(d=\gcd(a,b)\) ，有 \(d\mid a,~d\mid b\) ，因此 \(d\mid r\)，于是我们发现 \(\gcd(b,r)=d=\gcd(a,b)\) .

综上，\(\gcd (a,b)=\gcd(b,a\bmod b)\) ，于是我们可以利用这个性质不断递归求解直到 \(b=0\) ，这时候的 a 就是 gcd 了.

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

当整数的数量大于 2 时，我们求解前两个数的 gcd 与后一个数的 gcd ，便得到前 3 个数的 gcd ，依次进行下去，最后得到的便是这 n 个数的 gcd .

对了，这个算法就是欧几里得算法 .

最小公倍数

LCM ，即 Least Common Multiple .

一组整数的公倍数，是指同时是这组数中每一个数的倍数的数 . 0 是任意一组整数的公倍数 .

一组整数的最小公倍数，是指所有正的公倍数里面，最小的一个数 .

语言贫瘠，直接蒯 oi-wiki 上的了

同样也是先考虑两个数 \(a,b\) 的情况 .

将 \(a,b\) 写成素数的乘积的形式 .

\[a=p_1^{k_{a_1}}p_2^{k_{a_2}}\cdots p_n^{k_{a_{n}}}\]
\[b=p_1^{k_{b_1}}p_2^{k_{b_2}}\cdots p_n^{k_{b_{n}}}\]

根据定义可知 ，

\[\operatorname{lcm}(a,b)=p_1^{\min(k_{a_1},k_{b_1})}p_2^{\min(k_{a_2},k_{b_2})}\cdots p_n^{\min(k_{a_n},k_{b_{n}})}\]
\[\gcd(a,b)=p_1^{\max(k_{a_1},k_{b_1})}p_2^{\max(k_{a_2},k_{b_2})}\cdots p_n^{\max(k_{a_n},k_{b_{n}})}\]

而 \(\max(a,b)+\min(a, b)=a+b\) ，因此 \(\gcd(a,b)\times\operatorname{lcm}(a,b)=a\times b\) .

所以 \(\operatorname{lcm}(a,b)=\dfrac{a\times b}{\gcd(a,b)}\) .

对于多于 2 的整数数目的情况，处理方法和 gcd 是一样的 .

扩展欧几里得算法

扩展欧几里得算法（Extended Euclidean algorithm, EXGCD）常用来求解 \(ax+by=\gcd(a,b)\) 的一组可行解的情况 .

我们设 \(ax_1+by_1=\gcd(a,b)\) ，\(bx_2+(a\bmod b)y_2=\gcd(b,a\bmod b)\) .

下面我们来看看 \(x_1,y_1\) 和 \(x_2,y_2\) 之间的关系 .

将 \(a\bmod b=a-\lfloor\frac{a}{b}\rfloor\times b\) 和 \(\gcd(a,b)=\gcd(b,a\bmod b)\) 带入第二个方程，得到

\[bx_2+ay_2-\lfloor\frac{a}{b}\rfloor\times b\times y_2=\gcd(a,b)\]

整理得到

\[ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2)=\gcd(a, b)\]

与第一个方程比对可以发现 \(x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2\) .

因此我们可以不断递归求解 \(\gcd(a,b)\) 直到 \(b=0\) ，显然此时的 \(x_n=1\) ，然后考虑 \(x_{n-1},y_{n-1}\) 的情况，此时的 \(b=\gcd(a,b)\) ，而 \(a\not= 0\) ，所以 \(x_{n-1}=y_n=0\) ，综上，我们得到边界情况 \(x_n=1,y_n=0\) 同时求得了 \(\gcd(a,b)\) .

最后我们在不断回溯时修改 \(x,y\) 的值即可得到 \(ax+by=\gcd(a, b)\) 的一组可行解 .

int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int ret = exgcd(b, a % b, x, y);
    int tmp = x;
    x = y, y = tmp - a / b * y;
    return ret;
}

之后我们考虑整系数不定方程 \(ax + by = c\) 的求解。

首先，由裴蜀定理可以知道当且仅当 \(\gcd(a, b)\mid c\) 时有解，若 \(x=x_0, y=y_0\) ，则方程的所有整数解可以表示为

\[ \begin{cases} &x = x_0 - \dfrac{b}{(a, b)}t \\ &y = y_0 + \dfrac{a}{(a, b)}t \end{cases}, t \in \mathbb{Z} \]

更数论一点的解法在基础数论中已经给出，这里分享一个线性代数角度的解法。

不难将方程写成解线性方程组的矩阵形式，即方程等价于

\[ \begin{bmatrix} a & b \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = c \]

若我们已经得到特解 \(x = x_0, y = y_0\) ，那么只需求出

\[ \begin{bmatrix} a & b \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = 0 \]

的所有解即可，我们不难得到这个方程的特解为 \(x^{\prime}_0 = -\dfrac{b}{(a, b)}, y^{\prime}_0 = \dfrac{a}{(a, b)}\) （因为后面的 \(t\) 只能取整数，为了保证取完解空间下的所有整数解，所以此处的 \(x_0^{\prime}\) 和 \(y_0^{\prime}\) 必须要互质），于是便得到了原方程的所有解，为

\[ \begin{cases} &x = x_0 - \dfrac{b}{(a, b)}t \\ &y = y_0 + \dfrac{a}{(a, b)}t \end{cases}, t \in \mathbb{Z} \]

Comments