欧几里得算法
定义
欧几里得算法用于求两个正整数的最大公因数,其内容为:设\(\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\),终止递归。
实现
1 | int gcd(int a,int b) |