gcd算法

gcd算法

欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的正整数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

证明：

a可以表示成a = kb + r（a，b，k，r皆为正整数，且r<b），则r = a mod b

第一步：令c=gcd(a,b)，则设a=mc，b=nc

第二步：可知r =a-kb=mc-knc=(m-kn)c

第三步：根据第二步结果可知c也是r的因数

第四步：可以断定m-kn与n互素【否则，可设m-kn=xd,n=yd,(d>1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公约数≥cd，而非c，与前面结论矛盾】

从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)，得证

简单代码实现：

int` `gcd(``int` `a，``int` `b)
{
    ``if` `(a < b)
        ``std::swap(a, b);
    ``return` `b == 0 ? a : gcd(b, a % b);
}