欧几里得最大公约数算法
最大公约数
想必大家小学就学过什么事最大公约数吧，现在给出一个数学上的定义：定义$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); }
正文到此结束
热门推荐
相关文章
近期评论
-
你这基本没有更新呀，最近文章显示还是2019年的文章。不符合要求哈
-
关键词：慕云博客 链接：https://www.lilun.me 描述：分享原创文字的个人博客
-
-
-
可以提供一下源码吗
-
不是商业站，鸡娃学习笔记
-
-
-
-
听他们说很厉害的样子
Loading...
![[HBLOG]公众号](http://www.liuhaihua.cn/img/qrcode_gzh.jpg)
