扩展欧几里得算法（中国剩余定理、孙子定理）-程序员宅基地

前面一篇文章中我说了有一种叫做辗转相除的算法，今天做哦题目的时候又看到了一种新的算法（毕竟萌新）。

回归正题，今天我介绍的是扩展欧几里得算法，他能在求出两个整数a,b的最大公约数的同时，求出满足方程（a*x+b*y=gcd（a,b））的一组解（x,y）；

原理：

根据欧几里得算法：

gcd(a,b)=gcd(b,a mod b);

由于a*x+b*y=gcd(a,b)

所以我们有：

b*x1+(a mod b)*y1=gcd(b,a mod b);

化简得到：

=a*y1+b*(x1-a/b*y1);

所以我们有：

x=y1;

y=x1-a/b*y1;

自然想到，这是一个递归调用的问题。

下面是一个网上流行版本的扩展欧几里得算法模板：

int exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	int r=exgcd(b,a%b,x,y);
	int t=x;
	x=y;
	y=t-a/b*y;
	return r;
}

本文链接：https://blog.csdn.net/Ivanzn/article/details/79616791

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

智能推荐

【机器学习】一文搞懂标准化，归一化，正则化_机器学习标准化_Coder_preston的博客-程序员宅基地

归一化（Normalization）: 将一列数据变化到某个固定区间（范围）中，通常，这个区间是[0,1],广义的讲，可以是各种区间，比如映射到[0,1] 也可以映射到其他范围，在图像中可能会映射到[0, 255], 其他情况也有可能映射到[-1,1];最大值最小值的归一化,范围[0,1]均值归一化（Mean normalization）, 范围[-1,1]标准化(Standardization): 将数据变换为均值为0，标准差为1的分布。标准化=Xi−μσ。_机器学习标准化

t作用c语言,c语言中\t是什么意思_后端开发-程序员宅基地

typedef在c语言中是什么意思_后端开发typedef为C语言的关键字，作用是为一种数据类型定义一个新名字，这里的数据类型包括内部数据类型【int,char等】和自定义的数据类型【stuct等】。C语言的【\t】代表的意思是水平制表符，相当于按了键盘上的TAB按键，通常宽度相当于8个空格的位置，但有些软件允许设置tab的宽度，在双引号或定界符表示的字符串中有效，在单引号表示的字符串中无效。C语...

基于Matlab的压力控制论文,基于Matlab \ Simulink的气体辅助注射压力控制系统的建模与仿真...-程序员宅基地

第 17卷第5期奄锋垃专瓣．75 计算机仿真睫龟猢年 9月基 0～ Matlab＼Simulink的气体辅助注射压力摘要谖文推导出气体辅助注射压力控制系统的教学模型．井用控制系境计算机仿真软件——Mnhb的仿真1 具箱—— r 进行仿真。谈模型对气体辅助注射压力控制系境的设计和气体辅助注射成型：艺参数的研究都具胄实际的应用价值。关键词气体辅助注射 r 建模仿..._气罐压力控制matlab仿真

ASP.NET网站制作_asp.net网页制作-程序员宅基地

ASP.NET网站制作1、ASP.NET页面对象1网页脚本当客户端通过客户浏览器发送HTTP请求时，web服务器将HTML文档部分和脚本部分返回给客户端浏览器，在客户端浏览器中解释执行并及时更新页面，脚本处理工作全部在客户端浏览器执行完成。优点：减轻服务器负荷，同时增加页面的反应速度。缺点：浏览器差异性导致页面差异支持的语言： JavaScriptJScript VBScript（2）服务端脚本..._asp.net网页制作

泛型编程与设计新思维------这是一篇引用别人的文章-程序员宅基地

泛型编程与设计新思维 ------这是一篇引用别人的文章徐景周前言　　永远记住，编写代码的宗旨在于简单明了，不要使用语言中的冷僻特性，耍小聪明，重要的是编写你理解的代码，理解你编写的代码，这样你可能会做的更好。 --- Herb Sutter 　　1998年，国际C++标准正式通过，标准化对C++最重要的贡献是：对"强大的抽象概念"给于更有力的支持，以降低软件的复杂度，C++提供了二种功能强大的

Ubuntu16.04服务器Nginx配置反向代理tomcat-程序员宅基地

一、安装Nginx执行命令：sudo apt-get install nginxUbuntu下安装目录默认:/usr/sbin/nginx：主程序 /etc/nginx：存放配置文件 /usr/share/nginx：存放静态文件 /var/log/nginx：存放日志安装完成后，Nginx会自动启动，然后在浏览器输入服务器域名或ip访问，出现下面的页面则表示Ng...