WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
数学部分简介
符号
复数
位运算
快速幂
进位制
高精度计算
平衡三进制
素数
最大公约数
欧拉函数
筛法
欧拉定理 & 费马小定理
类欧几里德算法
裴蜀定理
乘法逆元
线性同余方程
中国剩余定理
二次剩余
BSGS
原根
卢卡斯定理
莫比乌斯反演
杜教筛
Min_25 筛
分解质因数
多项式部分简介
拉格朗日插值
快速傅里叶变换
快速数论变换
快速沃尔什变换
多项式求逆
多项式开方
多项式除法|取模
多项式对数函数|指数函数
多项式牛顿迭代
多项式多点求值|快速插值
多项式三角函数
多项式反三角函数
常系数齐次线性递推
生成函数简介
普通生成函数
指数生成函数
向量
矩阵
高斯消元
线性基
线性规划简介
单纯形算法
排列组合
卡特兰数
斯特林数
贝尔数
伯努利数
康托展开
容斥原理
抽屉原理
概率初步
置换群
斐波那契数列
博弈论
牛顿迭代法
数值积分
分段打表
64 objects
本站非官方,所收集资源均来源于网络。
最大公约数 - 数学
## 最大公约数 最大公约数即为 Greatest Common Divisor,常缩写为 gcd。 在 [素数](#) 一节中,我们已经介绍了约数的概念。 一组数的公约数,是指同时是这组数中每一个数的约数的数。而最大公约数,则是指所有公约数里面最大的一个。 那么如何求最大公约数呢?我们先考虑两个数的情况。 ### 欧几里得算法 如果我们已知两个数 $a$ 和 $b$ ,如何求出二者的最大公约数呢? 不妨设 $a > b$ 我们发现如果 $b$ 是 $a$ 的约数,那么 $b$ 就是二者的最大公约数。 下面讨论不能整除的情况,即 $a = b \times q + r$ ,其中 $r < b$ 。 我们通过证明可以得到 $\gcd(a,b)=\gcd(b,a \bmod b)$ ,过程如下: * * * 设 $a=bk+c$ ,显然有 $c=a \bmod b$ 。设 $d \mid a,~d \mid b$ ,则 $c=a-bk, \frac{c}{d}=\frac{a}{d}-\frac{b}{d}k$ 。 由右边的式子可知 $\frac{c}{d}$ 为整数,即 $d \mid c$ 所以对于 $a,b$ 的公约数,它也会是 $a \bmod b$ 的公约数。 反过来也需要证明: 设 $d \mid b,~\mid (a \bmod b)$ ,我们还是可以像之前一样得到以下式子 $\frac{a\bmod b}{d}=\frac{a}{d}-\frac{b}{d}k,~\frac{a\bmod b}{d}+\frac{b}{d}k=\frac{a}{d}$ 。 因为左边式子显然为整数,所以 $\frac{a}{d}$ 也为整数,即 $d \mid a$ ,所以 $b,a\bmod b$ 的公约数也是 $a,b$ 的公约数。 既然两式公约数都是相同的,那么最大公约数也会相同。 所以得到式子 $\gcd(a,b)=\gcd(b,a\bmod b)$ 既然得到了 $\gcd(a, b) = \gcd(b, r)$ ,这里两个数的大小是不会增大的,那么我们也就得到了关于两个数的最大公约数的一个递归求法。 ```cpp int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } ``` 递归至 `b==0` (即上一步的 `a%b==0` ) 的情况再返回值即可。 上述算法被称作欧几里得算法(Euclidean algorithm)。 如果两个数 $a$ 和 $b$ 满足 $\gcd(a, b) = 1$ ,我们称 $a$ 和 $b$ 互质。 * * * 欧几里得算法的时间效率如何呢?下面我们证明,欧几里得算法的时间复杂度为 $O(\log n)$ 。 当我们求 $\gcd(a,b)$ 的时候,会遇到两种情况: - $a < b$ ,这时候 $\gcd(a,b)=\gcd(b,a)$ ; - $a \geq b$ ,这时候 $\gcd(a,b)=\gcd(b,a \bmod b)$ ,而对 $a$ 取模会让 $a$ 至少折半。这意味着这一过程最多发生 $O(\log n)$ 次。 第一种情况发生后一定会发生第二种情况,因此第一种情况的发生次数一定 **不多于** 第二种情况的发生次数。 从而我们最多递归 $O(\log n)$ 次就可以得出结果。 事实上,假如我们试着用欧几里得算法去求 [斐波那契数列](#) 相邻两项的最大公约数,会让该算法达到最坏复杂度。 ### 多个数的最大公约数 那怎么求多个数的最大公约数呢?显然答案一定是每个数的约数,那么也一定是每相邻两个数的约数。我们采用归纳法,可以证明,每次取出两个数求出答案后再放回去,不会对所需要的答案造成影响。 ## 最小公倍数 接下来我们介绍如何求解最小公倍数(Least Common Multiple, LCM)。 ### 两个数的 首先我们介绍这样一个定理——算术基本定理: > 每一个正整数都可以表示成若干整数的乘积,这种分解方式在忽略排列次序的条件下是唯一的。 用数学公式来表示就是 $x = p_1^{k_1}p_2^{k_2} \cdots p_s^{k_s}$ 设 $a = p_1^{k_{a_1}}p_2^{k_{a_2}} \cdots p_s^{k_{a_s}}$ , $b = p_1^{k_{b_1}}p_2^{k_{b_2}} \cdots p_s^{k_{b_s}}$ 我们发现,对于 $a$ 和 $b$ 的情况,二者的最大公约数等于 $p_1^{\min(k_{a_1}, k_{b_1})}p_2^{\min(k_{a_2}, k_{b_2})} \cdots p_s^{\min(k_{a_s}, k_{b_s})}$ 最小公倍数等于 $p_1^{\max(k_{a_1}, k_{b_1})}p_2^{\max(k_{a_2}, k_{b_2})} \cdots p_s^{\max(k_{a_s}, k_{b_s})}$ 由于 $k_a + k_b = \max(k_a, k_b) + \min(k_a, k_b)$ 所以得到结论是 $\gcd(a, b) \times \operatorname{lcm}(a, b) = a \times b$ 要求两个数的最小公倍数,先求出最大公约数即可。 ### 多个数的 可以发现,当我们求出两个数的 $\gcd$ 时,求最小公倍数是 $O(1)$ 的复杂度。那么对于多个数,我们其实没有必要求一个共同的最大公约数再去处理,最直接的方法就是,当我们算出两个数的 $\gcd$ ,或许在求多个数的 $\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)$ 由欧几里得定理可知: $\gcd(a,b)=\gcd(b,a\bmod b)$ 所以 $ax_1+by_1=bx_2+(a\bmod b)y_2$ 又因为 $a\bmod b=a-(\lfloor\frac{a}{b}\rfloor\times b)$ 所以 $ax_1+by_1=bx_2+(a-(\lfloor\frac{a}{b}\rfloor\times b))y_2$ $ax_1+by_1=ay_2+bx_2-\lfloor\frac{a}{b}\rfloor\times by_2=ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2)$ 因为 $a=a,b=b$ ,所以 $x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2$ 将 $x_2,y_2$ 不断代入递归求解直至 $\gcd$ (最大公约数,下同)为 `0` 递归 `x=1,y=0` 回去求解。 ```cpp int Exgcd(int a, int b, int &x, int &y) { if (!b) { x = 1; y = 0; return a; } int d = Exgcd(b, a % b, x, y); int t = x; x = y; y = t - (a / b) * y; return d; } ``` 函数返回的值为 $\gcd$ ,在这个过程中计算 $x,y$ 即可。 ### 迭代法编写拓展欧几里得算法 因为迭代的方法避免了递归,所以代码运行速度将比递归代码快一点。 ```cpp int gcd(int a, int b, int& x, int& y) { x = 1, y = 0; int x1 = 0, y1 = 1, a1 = a, b1 = b; while (b1) { int q = a1 / b1; tie(x, x1) = make_tuple(x1, x - q * x1); tie(y, y1) = make_tuple(y1, y - q * y1); tie(a1, b1) = make_tuple(b1, a1 - q * b1); } return a1; } ``` 如果你仔细观察 $a_1$ 和 $b_1$ ,你会发现,他们在迭代版本的欧几里德算法中取值完全相同,并且以下公式无论何时(在 while 循环之前和每次迭代结束时)都是成立的: $x \cdot a +y \cdot b =a_1$ 和 $x_1 \cdot a +y_1 \cdot b= b_1$ 。因此,该算法肯定能正确计算出 $\gcd$ 。 最后我们知道 $a_1$ 就是要求的 $\gcd$ ,有 $x \cdot a +y \cdot b =g$ 。 ## 应用 - [10104 - Euclid Problem](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1045) - [GYM - (J) once upon a time](http://codeforces.com/gym/100963) - [UVA - 12775 - Gift Dilemma](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4628)