欧几里得算法

定义

欧几里得算法用于求两个正整数的最大公因数，其内容为：设\(\gcd(a,b)\)为正整数\(a,b\)的最大公因数，则\(\gcd(a,b)=\gcd(b,a \bmod b)\)。

求解算法

思路与简单证明

不妨设\(\gcd(a,b)=c,a>b,\lfloor \frac ab\rfloor=k,a \bmod b=r\)；

令\(a=mc,b=nc\)，易得\(\gcd(m,n)=1\)；

代入得\(r=a-bk=mc-nck=(m-nk)c\)；

若要证\(\gcd(a,b)=\gcd(b,r)=c\)，就要证\(\gcd(n,m-nk)=1\)；

假设\(\gcd(n,m-nk)=d\neq 1\)；

设\(n=xd,m-nk=yd\)；

代入得\(m=ydk+xd=(x+yk)d\)；

得\(\gcd(n,m)=d\neq 1\)，与\(\gcd(n,m)=1\)矛盾，故假设不成立，即\(\gcd(n,m-nk)=1\)，故得证；

于是我们可以递归实现，边界条件：设在第\(k\)层递归\(b_k=0\)，即第\(k-1\)层递归\(a_{k-1} \bmod b_{k-1}=0\)时，可得\(a_{k-1}\)是\(b_{k-1}\)的倍数，即\(\gcd(a_{k-1},b_{k-1})=b_{k-1}\)，得出\(\gcd(a_1,b_1)=b_{k-1}\)；

故可在第\(k\)层递归返回\(a_k\)，终止递归。

实现

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