欧几里得算法

基础:设有几个数\(a,b,c\)若\(a|b\)且\(a|c\)则\(a|b+c\)故而我们可以推出\(a|xb+yc\)我们可以推出\((a,b) = (b,a\mod b)\)

注：()是括号内两个数公约数集合

​ |是整除得意思。

证明：因为\(a \mod b == a - [\frac a b]*b\)故而我们根据上述定理。设左边任何一个公约数为\(d\),由已知得：\(d|a\) 且 \(d|b\) 故 \(d|(a -[\frac b a]* b)\),故a得任何一个公约数都存在于\((b,a \mod b)\)里面。所以我们可以辗转相除，不断的迭代，直到最后\(a\mod b== 0\)的时候，因为0是能整除所有数，故传递过去的b就为最大公约数。

代码:

int gcd(int a,int b)
{
    if(!b) return a;
    gcd(b,a % b);
}