本文共 1288 字，大约阅读时间需要 4 分钟。

众所周知，求最大公约数一般辗转相除，代码很短，主要在于证明

int gcd(int x,int y){       if(y==0) return x;    else return gcd(y,x%y);}

也可以写为

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

时间复杂度是$O(log(a+b))$，比试除法划算多了。

代码很短，主要看证明。

一开始我想的是设$x$和$y$的最大公约数为$a$

则$x=m\times a$，$y=n\times a$，(这里先保证$x>y$) $m$和$n$为互质数 所以$x-y=(m-n)\times a$ 此时$x-y$与$x$的最大公约数还是$a$

但是这里就忽略了一个问题：

我不会证明当$m$和$n$为互质数的时候$(m-n)$与$m$和$n$中的任意一个数也是互质数！

所以此方法不够严谨。

当这个博客发出去第一次后，我突发奇想可以加上反证法：

已知$m$和$n$为互质数，若$(m-n)$和$m$不为互质数

则有$(m-n)=q\times t$，$m=p\times t$，($t$为大于$1$的整数) 那么$n=(m-(m-n))=(p-q)\times t$ 这样的话$n$和$m$就不是互质数了 所以假设不成立 这样的话$gcd(x,y)$就等于$gcd(y,x-y)$ 而$mod$就相当于是减去了$a$就相当于$a$减去了$k$个$b$ 这样就省去了很多减的运算 辗转相除到最后，其中一个数为$0$时 另一个数即为原来两数的最大公因数

由定义“$\forall x,y\in \mathbb{N}$，$gcd(a,b)\times lcm(a,b)=a\times b$”可得

int lcm(int x,int y){   	return (a*b/gcd(a,b));}

例题：

$\bullet$ $\bullet$

转载地址：http://slro.baihongyu.com/