当前位置: 首页> 房产> 家装 > 网站搭建徐州百度网络_央视新闻最新消息今天_重庆网站建设公司_美国疫情最新消息

网站搭建徐州百度网络_央视新闻最新消息今天_重庆网站建设公司_美国疫情最新消息

时间:2025/7/10 13:51:55来源:https://blog.csdn.net/WenBayBay/article/details/144974578 浏览次数:0次
网站搭建徐州百度网络_央视新闻最新消息今天_重庆网站建设公司_美国疫情最新消息

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

        依据的基本定理:

                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;
}

        

关键字:网站搭建徐州百度网络_央视新闻最新消息今天_重庆网站建设公司_美国疫情最新消息

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: