辗转相除法求最大公约数是一种常用的求两个数的最大公约数的方法。
方法是：以小数除大数，如果能整除，那么小数就是所求的最大公约数。
否则就用余数来除除数；再用新除法的余数去除刚才的余数。
依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数。
证明
证明思路
先假设
d
d
d
是
a
，
b
a，b
a
，
b
的公约数，证明
d
d
d
也是
b
b
b
,
a
a
a
m
o
d
mod
m
o
d
b
b
b
的公约数。
再假设
d
d
d
是
b
b
b
,
a
a
a
m
o
d
mod
m
o
d
b
b
b
的公约数,证明
d
d
d
也是
a
,
b
a,b
a
,
b
的公约数。
最后推出
(
a
,
b
)
(a,b)
(
a
,
b
)
和
(
b
,
a
(b,a
(
b
,
a
m
o
d
mod
m
o
d
b
)
b)
b
)
的公约数是一样的。
具体证明
a
a
a
可以表示成
a
=
k
b
+
r
a = kb + r
a
=
k
b
+
r
（
a
，
b
，
k
，
r
皆
为
正
整
数
，
且
r
<
b
）
（a，b，k，r皆为正整数，且r<b）
（
a
，
b
，
k
，
r
皆
为
正
整
数
，
且
r
<
b
）
，则
r
=
a
r = a
r
=
a
m
o
d
mod
m
o
d
b
b
b
假设
d
d
d
是
a
,
b
a,b
a
,
b
的一个公约数，记作
d
∣
a
,
d
∣
b
d|a,d|b
d
∣
a
,
d
∣
b
，即
a
a
a
和
b
b
b
都可以整除
d
d
d
。
而
r
=
a
−
k
b
r = a – kb
r
=
a
−
k
b
，两边同时除以
d
d
d
，
r
/
d
=
a
/
d
−
k
b
/
d
=
m
r/d=a/d-kb/d=m
r
/
d
=
a
/
d
−
k
b
/
d
=
m
，
由等式右边可知
m
m
m
为整数，因此
d
∣
r
d|r
d
∣
r
因此
d
d
d
也是
b
b
b
,
a
a
a
m
o
d
mod
m
o
d
b
b
b
的公约数。
假设
d
d
d
是
b
b
b
,
a
a
a
m
o
d
mod
m
o
d
b
b
b
的公约数, 则
d
∣
b
,
d
∣
(
a
−
k
∗
b
)
,
k
d|b,d|(a-k*b),k
d
∣
b
,
d
∣
(
a
−
k
∗
b
)
,
k
是一个整数。
进而
d
∣
a
d|a
d
∣
a
.因此
d
d
d
也是
a
,
b
a,b
a
,
b
的公约数。
因此
(
a
,
b
)
(a,b)
(
a
,
b
)
和
(
b
,
a
(b,a
(
b
,
a
m
o
d
mod
m
o
d
b
)
b)
b
)
的公约数是一样的，其最大公约数也必然相等，得证。
最大公约数
代码实现非常简单。。
由上面的证明可以发现最大公约数具有递归性质，即
(
a
,
b
)
(a,b)
(
a
,
b
)
的最大公约数和
(
b
,
a
(b,a
(
b
,
a
m
o
d
mod
m
o
d
b
)
b)
b
)
的最大公约数相等，由
(
a
,
b
)
(a,b)
(
a
,
b
)
转化为其子问题
(
b
,
a
(b,a
(
b
,
a
m
o
d
mod
m
o
d
b
)
b)
b
)
。
最后，若
b
∣
a
b|a
b
∣
a
，那么
a
a
a
m
o
d
mod
m
o
d
b
=
0
b=0
b
=
0
，就是递归边界。
#define LL long long
LL gcd(LL a,LL b) //最大公约数
{
if(b==0)
return a;
return gcd(b,a%b);
}
最小公倍数
就是两个数相乘，然后除以他们的最大公约数。
LL lcm(LL a,LL b) //最小公倍数
{
return a*b/gcd(a,b);
}