好的高端网站,wordpress文章框,关键帧,做公众号推送的网站欧几里得算法用于求解两个整数的最大公约数#xff0c;又称为辗转相除 依据的基本定理#xff1a; GCD(a,b)GCD(a%b,b) 证明#xff1a; 对于搞理论的人可能需要会严格证明#xff0c;但是对于我们一般人而言#xff0c;只要能理解其原理并记住即可#xff0c;后者实际上… 欧几里得算法用于求解两个整数的最大公约数又称为辗转相除 依据的基本定理 GCD(a,b)GCD(a%b,b) 证明 对于搞理论的人可能需要会严格证明但是对于我们一般人而言只要能理解其原理并记住即可后者实际上是非常简单的且看 如果我们有两个数a, b假设其最大公约数m 那么有a%m0b%m0 那么我们是不是可以将a看成k*bc那么(k*bc)%m(k*b)%mc%m0c%m容易发现m也正是b与c的最大公约数 所以求a与b的最大公约数也就是求ca%b与b的最大公约数于是基本定理就是这么来的 GCD(a,b)GCD(a%b,b) 那么这样辗转相除下去最后一定会得到0 如果a是b的最大公约数m非1那么得到(0,m)最大公约数就是m 如果不是那么最后a%b一定得1即(1,b)然后b%10最后得01最大公约数就是1 这里需要注意参数顺序, 要么: GCD(a,b)GCD(b,a%b) GCD(a,b)GCD(b%a,b) 不能写成GCD(a,b)GCDa%b,b)这样会死递归 那么代码就可以写了 int GCD(int a,int b)
{return a?GCD(b%a,a):b;
}
