吐鲁番市建设局网站百度云网盘资源分享网站

        欧几里得算法用于求解两个整数的最大公约数，又称为辗转相除

        依据的基本定理：

                GCD(a,b)=GCD(a%b,b)

证明：

        对于搞理论的人可能需要会严格证明，但是对于我们一般人而言，只要能理解其原理并记住即可，后者实际上是非常简单的，且看：

        如果我们有两个数a, b，假设其最大公约数m

        那么有a%m==0，b%m==0

        那么我们是不是可以将a看成k*b+c，那么(k*b+c)%m=(k*b)%m+c%m=0+c%m，容易发现m也正是b与c的最大公约数，

        所以求a与b的最大公约数，也就是求c=a%b与b的最大公约数，于是基本定理就是这么来的：        

•                 GCD(a,b)=GCD(a%b,b)

        那么这样辗转相除下去，最后一定会得到0，

        如果a是b的最大公约数m非1，那么得到(0,m)，最大公约数就是m

        如果不是，那么最后a%b一定得1，即(1,b)，然后b%1==0，最后得（0，1），最大公约数就是1

        这里需要注意参数顺序, 要么:

                GCD(a,b)=GCD(b,a%b)

                GCD(a,b)=GCD(b%a,b)

        不能写成GCD(a,b)=GCD（a%b,b)，这样会死递归

        那么代码就可以写了：

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