最大公约数

最大公约数与最小公倍数

最大公约数：若干数的最大的共同约数，记作 $g c d$ 。

最小公倍数：若干数的最小的共同倍数，记作 $l c m$ 。

设 $a = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{n}^{k_{n}}$ ， $b = p_{1}^{t_{1}} p_{2}^{t_{2}} \dots p_{n}^{t_{n}}$ 。

$a, b$ 的最大公约数等于 $p_{1}^{m i n (k_{1}, t_{1})} p_{2}^{m i n (k_{2}, t_{2})} \dots p_{n}^{m i n (k_{n}, t_{n})}$ 。

$a, b$ 的最小公约数等于 $p_{1}^{m a x (k_{1}, t_{1})} p_{2}^{m a x (k_{2}, t_{2})} \dots p_{n}^{m a x (k_{n}, t_{n})}$ 。

因为 $m i n (a, b) + m a x (a, b) = a + b$ 。

所以 $p_{1}^{m i n (k_{1}, t_{1})} * p_{1}^{m a x (k_{1}, t_{1})} = p_{1}^{k_{1}} * p_{1}^{t_{1}}$

所以 $ a*b = gcd(a,b)lcm(ab)$。

多个数的最大公约数： $g c d (a_{1}, a_{2}, a_{3}) = g c d (g c d (a_{1}, a_{2}), a_{3})$ 。

多个数的最小公倍数： $l c m (a_{1}, a_{2}, a_{3}) = l c m (l c m (a_{1}, a_{2}), a_{3})$ 。

更相减损术

若要求两个数字 $a, b$ 的最大公约数。

假设 $a, b$ 的最大公约数为 $g$ ，则

$a = k_{1} g$ ， $b = k_{2} g$ 。

所以两个互相加减并不会影响他们是 $g$ 的倍数。

自然想到：每次用 $a, b$ 中大的去减去小的，直到某个数字变成 $0$ ，则另一个数字恰好是最大公约数 $g$ 。

cpp

int gcd(int a,int b)
{
    if(a==0||b==0) return a+b;
    if(a<b) swap(a,b);
    return gcd(a-b,b);
}

时间复杂度 $O (m a x (a, b))$ 。

辗转相除法

又称欧几里得算法

一直用大的数减去小的数，其实可以用取模一步到位。

cpp

int gcd(int a,int b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}

因为每次取模至少会让数字变为原来的一半，所以时间复杂度是 $O (l o g_{2} a)$ 。

当我们求 $n$ 个数的最大公约数时，时间复杂度是多少？

表面上是 $O (n * l o g_{2} a)$ 。

实际上，最大公约数只会单方向变小，所以是 $O (n + l o g_{2} a)$ 。

二进制数最大公约数

求两个二进制大整数 $a, b$ 的最大公约数

分类讨论：

$a, b$ 都是偶数：

g c d (a, b) = 2 * g c d (\frac{a}{2}, \frac{b}{2})

$a$ 奇数， $b$ 偶数：

g c d (a, b) = g c d (a, \frac{b}{2})

$a, b$ 都是奇数：

g c d (a, b) = g c d (a - b, b)

除以二可以用删除最后一位代替。

当 $a, b$ 都是奇数时， $a - b$ 会变成偶数，所以每两步至少有一个数字变成原来的 $\frac{1}{2}$ ，时间复杂度仍然是 $O (l o g_{2} a)$ 。

用这种方法避免了转换成十进制以及写高精度取模等复杂度操作。

练习题

P4057 [Code+#1] 晨跑

I'm bored with life

P8792 [蓝桥杯 2022 国 A] 最大公约数

P1072 [NOIP2009 提高组] Hankson 的趣味题

公因子