【知识学习】最大公因数gcd_证明最大公约数反复应用递归部分可以把公式右侧的gcd表达式转变为基础部分的-程序员宅基地

技术标签：知识学习 gcd

前

最大公因数，又叫gcd/最大公约数。

解决的两大算法：更相减损辗转相除

以下附简单证明

中

更相减损

记住：这是我们中国人的算法！

用大数减小数的差和小数的最大公约数与原来两个数的最大公约数相等

证明：
在这里插入图片描述

代码实现

int gcd(int x , int y) {
    
	if(x==y) return x;
	if(x<y)
		return gcd(y-x , x);
	return gcd(x-y , y);
}

辗转相除

又叫欧几里得算法

证明：
在这里插入图片描述
稍微解释一下上面的证明（证明来自百度百科）

从上到下看下来应该也就是倒数第四行的结论可能有问题吧，其实可以知道 $m$ 和 $n$ 是互质的（因为如果不互质，则第一行假设不成立），所以y%x一定不等于零，所以 $y + k x$ 一定与 $x$ 互质，那么就有倒数第四行的“可得”了。

代码实现：

int gcd(int x , int y) {
    
	return y==0?x:gcd(y,x%y);
}

后

忘记好多知识点了，第一遍学的时候也不仔细也没搞懂原理

希望大家这一遍看过就真的搞懂这个算法，手推一下证明过程哦

本文链接：https://blog.csdn.net/cls1277/article/details/108763142

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

php-读取excel文件_php 读取excel-程序员宅基地

文章浏览阅读373次。php-读取excel文件_php 读取excel

（2022，FreGAN）利用频率分量在有限数据下训练 GAN-程序员宅基地

文章浏览阅读522次，点赞4次，收藏7次。GAN 在拟合数据分布时，往往倾向于拟合低频信息而忽略高频信息。本文提出了一种称为 FreGAN 的频率感知模型，以提高 G 和 D 的频率感知能力。通过鼓励 G 生成更合理高频信号，从而提高有限数据下的合成性能。_fregan

pyc文件逆向_攻防世界python-trade_逆向之旅010_逆向 pyc base64-程序员宅基地

文章浏览阅读1.5k次，点赞3次，收藏8次。使用工具easy python Decompiler 将pyc文件反编译为py文件。我把这个工具放在百度云里了，按需自取，链接（永久）: 链接：https://pan.baidu.com/s/14iQRcHyAEpmmycTQZLbwlQ 提取码：3naj_逆向 pyc base64

Mac Node.JS本地卸载删除解决方案_mac 卸载本地nodejs-程序员宅基地

文章浏览阅读1k次。前言卸载Node.JS操作步骤，按住 command + 空格键搜索终端依次复制粘贴一下命令sudo npm uninstall npm -gsudo rm -rf /usr/local/lib/node /usr/local/lib/node_modules /var/db/receipts/org.nodejs.*sudo rm -rf /usr/local/include/node /Users/$USER/.npmsudo rm /usr/local/bi..._mac 卸载本地nodejs

Java虚拟机学习笔记整理_虚拟机的笔记-程序员宅基地

文章浏览阅读645次，点赞2次，收藏2次。一. JVM规范1.1 位运算1.1.1 整型int原码：第一位符号位，0为正，1为负反码：符号位不动，原码取反补码正数补码：和源码相同负数补码：符号位不动，反码加1 example-6原码： 10000110反码： 11111001补码： 11111010为何使用补码可以无歧义地表示0 不使用补码，将0看为正数：0000 0000 ..._虚拟机的笔记

蓝凌EIS智慧协同平台saveImg接口存在任意文件上传漏洞_蓝凌eis智慧协同平台文件上传漏洞-程序员宅基地

文章浏览阅读979次。蓝凌智慧协同平台eis集合了非常丰富的模块，满足组织企业在知识、协同、项目管理系统建设等需求。_蓝凌eis智慧协同平台文件上传漏洞

随便推点

enumerate（）用法_enumerate(a)-程序员宅基地

文章浏览阅读221次。for index , item in enumerate (a , x):for index , item in enumerate (a):这里有n，v俩参数，n先不管，v为a中的元素，比较简单。a=[[8,2],[2,3],[5,4]]print(a)for n , v in enumerate(a): v += v print(v) #print(n)输出[[8, 2], [2, 3], [5, 4]][8, 2, 8, 2][2, 3, 2, 3]_enumerate(a)

计算几何讲义——计算几何中的欧拉定理-程序员宅基地

文章浏览阅读188次。在处理计算几何的问题中，有时候我们会将其看成图论中的graph图，结合我们在图论中学习过的欧拉定理，我们可以通过图形的节点数(v)和边数(e)得到不是那么好求的面数f。平面图中的欧拉定理：定理：设G为任意的连通的平面图，则v-e+f=2，v是G的顶点数，e是G的边数，f是G的面数。证明：其实有点类似几何学中的欧拉公式的证明方法，这里采用归纳证明的方法。对m..._怎么证明平面图欧拉定理

c语言中各种括号的作用,C语言中各种类型指针的特性与用法介绍-程序员宅基地

文章浏览阅读750次。C语言中各种类型指针的特性与用法介绍本文主要介绍了C语言中各种类型指针的特性与用法，有需要的朋友可以参考一下!想了解更多相关信息请持续关注我们应届毕业生考试网!指针为什么要区分类型：在同一种编译器环境下,一个指针变量所占用的内存空间是固定的。比如,在16位编译器环境下,任何一个指针变量都只占用8个字节,并不会随所指向变量的类型而改变。虽然所有的指针都只占8个字节,但不同类型的变量却占不同的字节数..._c语言带括号指针

缅甸文字库缅甸语字库缅甸字库算法_0x103c-程序员宅基地

文章浏览阅读9.5k次。字库交流 QQ:2229691219 缅甸语比较特殊、缅甸语有官方和民间之分，二者不同的是编码机制不同，因此这2种缅甸语的字串翻译、处理引擎、字库都是不同的。我们这里只讨论官方语言。缅文、泰文等婆罗米系文字大多是元音附标文字，一般辅音字母自带默认元音可以发音，真正拼写词句时元音像标点符号一样附标在辅音上下左右的相应位置。由于每个元音位于辅音的具体位置是有自己的规则的，当只书写..._0x103c

Python+django+vue校园二手闲置物品拍卖系统pycharm毕业设计项目推荐_基于python+django+vue实现的校园二手交易平台-程序员宅基地

文章浏览阅读200次。在校园，随着学生数量的增多，存在许多生活和学习物品，许多学习用品经过一学期学习之后往往被闲置，一些出于一时喜欢而购买的物品使用机会少而被闲置，还有一些物品以低廉的价格卖给资源回收站，造成巨大的资源浪费。校园闲置物品拍卖系统使用python技术，MySQL数据库进行开发，系统后台使用django框架进行开发，具有低耦合、高内聚的特点，其中校园用户通过人脸识别的方法增加系统安全性，在闲置物品推荐中，使用协同过滤算法进行商品推荐。系统的开发，帮助高校有效的对闲置物品进行管理，提高了闲置物品销售的效率。_基于python+django+vue实现的校园二手交易平台

【推荐系统论文精读系列】(十)--Wide&Deep Learning for Recommender Systems_引用《wide & deep learning for recommender systems》-程序员宅基地

文章浏览阅读1.1k次，点赞3次，收藏3次。文章目录Wide & Deep Learning for Recommender Systems一、摘要二、介绍三、推荐系统综述四、Wide&Deep学习4.1 Wide部分4.2 Deep部分4.3 联合训练 Wide&Deep ModelPreferenceWide & Deep Learning for Recommender Systems一、摘要具有非线性特征转化能力的广义线性模型被广泛用于大规模的分类和回归问题，对于那些输入数据是极度稀疏的情况下。通过使用交_引用《wide & deep learning for recommender systems》