欧几里得算法

简单的求最大公因数算法证明

简介

欧几里得算法又称辗转相除法，用于求两数的最大公因数，在各种题目中很常见。
证明

$a,b$为整数，不妨设$a=kb+c\,(c=a\,mod\,b)$，下面证明$gcd(a,b)=gcd(b,a\,mod\,b)$。

一方面：
\[\begin{aligned} &设\,\, d|a,\,d|b\\ &有\,\,c=a-kb,\quad\frac{c}{d}=\frac{a}{d}-k\frac{b}{d}\\ &\frac{a}{d}-k\frac{b}{d}为整数=>d|c \end{aligned}\]
另一方面:
\[\begin{aligned} &设\,\,d|b,\,d|c\\ &有\,\,\frac{a}{d}=k\frac{b}{d}+\frac{c}{d}\\ &k\frac{b}{d}+\frac{c}{d}为整数=>d|a \end{aligned}\]
所以$a,b$的所有公因数也是$b,a\,mod\,b$的所有公因数，就得到$gcd(a,b)=gcd(b,a\,mod\,b)$，又因为$gcd(a,0)=a$所以重复上述过程直到第二项为0，第一项就是要求的最大公因数。
时间复杂度

当$a<b$时，$gcd(a,b)=gcd(b,a)$

当$a\geq b$时，由于每次a对b取模都会使a的大小最多变为a的一半，所以可以粗略的认为最差时间复杂度为$O(logn)$

严格证明参考拉梅定理
最大公倍数
\[\begin{aligned} &设\,\,a=p_1^{k_{a1}}p_2^{k_{a2}}...p_s^{k_{as}},\,\,b=p_1^{k_{b1}}p_2^{k_{b2}}...p_s^{k_{bs}}\\ &有\,\,gcd(a,b)=p_1^{min(k_{a1},k_{b1})}p_2^{min(k_{a2},k_{b2})}...p_s^{min(k_{as},k_{bs})}\\ &\quad lcm(a,b)=p_1^{max(k_{a1},k_{b1})}p_2^{max(k_{a2},k_{b2})}...p_s^{max(k_{as},k_{bs})}\\ &而\,\,k_{a}+k_{b}=min(k_{a},k_{b})+max(k_{a},k_{b})\\ &所以\,\,lcm(a,b)=\frac{a*b}{gcd(a,b)} \end{aligned}\]

代码

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