欧几里得最大公约数算法
最大公约数
想必大家小学就学过什么事最大公约数吧，现在给出一个数学上的定义：定义$g$是整数$a$和$b$的最大公约数，当且仅当$g$是同时整除$a$和$b$的数中最大的那个。
欧几里得算法
欧几里得算法可以写成如下简单的形式：
$$gcd(a,b) =/begin{cases} a, & /mbox{if }b=0 //gcd(b,a/ mod/ b), & /mbox{if }b/ne0/end{cases}$$
算法的证明
算法的过程可以写成如下的形式：
$$a=q_0b+r_0$$
$$b=q_1r_0+r_1$$
$$r_0=q_2r_1+r_2$$
$$r_1=q_3r_2+r_3$$
$$/cdots$$
$$r_{k-1}=q_{k+1}r_k$$
显然，欧几里得算法的答案就是$r_k$。
先证明$r_k$能整除$a$和$b$：
$$/because r_{k-1}=q_{k+1}r_k$$
$$/therefore r_{k-2}=q_kr_{k-1}+r_k=(q_{k+1}q_k+1)r_k$$
$$/therefore r_k/mid r_{k-2}$$
$$/cdots$$
$$/therefore r_k/mid b$$
$$/therefore r_k/mid a$$
$$/therefore gcd(a,b)=g/ge r_k$$
接下来证明$gcd(a,b)=g$能整除r_k
$$/mbox{令} a=ng/ b=mg$$
$$/because a=q_0b+r_0$$
$$/therefore r_0=a-q_0b=ng-q_0mg=(n-q_0m)g$$
$$/mbox{同理}g/mid r_k$$
$$/therefore g/le r_k$$
$$/mbox{由前面的证明我们知道} g/ge r_k$$
$$/therefore g=r_k$$
代码
int gcd(int a, int b){ return b==0?a:gcd(b,a%b); }
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
