扩展欧几里得算法

文章目录

  • 扩展欧几里得算法的内容及证明
  • 扩展欧几里得算法的代码实现
  • 扩展欧几里得算法的用途

本文的问题场景中,涉及到的变量均为整数。

扩展欧几里得算法的内容及证明

贝祖等式:
a x + b y = g c d ( a , b ) = c ax+by= gcd(a, b) = c ax+by=gcd(a,b)=c
其中 a a a b b b 为已知值, c c c a a a b b b 的最大公约数。 x x x y y y 为要求的方程变量。

贝祖等式就是说上述式子一定有解。

扩展欧几里得算法(贝祖等式)的证明:

由上一篇文章(欧几里得算法) 可知, g c d ( a , b ) = g c d ( b , a % b ) gcd(a, b) = gcd(b, a\%b) gcd(a,b)=gcd(b,a%b). 这样不断递归下去,最终能得到 g c d ( a , b ) = g c d ( b , a % b ) = . . . = g c d ( c , 0 ) gcd(a, b) = gcd(b, a \% b) = ... = gcd(c, 0) gcd(a,b)=gcd(b,a%b)=...=gcd(c,0)

然后在回溯的过程中,假设 a = c , b = 0 a = c, b = 0 a=c,b=0, 那么很容易得知当 x = 1 , y = 0 x = 1, y = 0 x=1,y=0 时, 有 a x + b y = c ax + by = c ax+by=c; 数学归纳法的思路,假设回溯在某一层 ( b , a % b ) (b, a \% b) (b,a%b) 时, 已经确定了 x x x y y y, 即
b x + ( a % b ) y = c \begin{align} bx + (a \% b) y = c \end{align} bx+(a%b)y=c
那么对于回溯的下一层 ( a , b ) (a, b) (a,b) , 需要确定 x ′ , y ′ x', y' x,y, 使得
a x ′ + b y ′ = c \begin{align}ax' + by' = c\end{align} ax+by=c
因为 $a % b $ 可以写成 a − k b a - kb akb 的形式,所以 ( 1 ) (1) (1) 式可以写为:

b x + ( a − k b ) y = c bx + (a - kb)y = c bx+(akb)y=c

整理得

a y + b ( x − k y ) = c \begin{align}ay + b(x - ky) = c\end{align} ay+b(xky)=c

于是令 x ′ = y , y ′ = x − k y x' = y, y' = x - ky x=y,y=xky 即可使得 ( 2 ) (2) (2) 式成立。

如下图所示:
在这里插入图片描述
这样贝祖等式就证明了一定有解,并且找到了一种求解的方式。这也就是扩展的欧几里得算法。

扩展欧几里得算法的代码实现

代码实现:

#include <iostream>

using namespace std;
int ex_gcd(int a, int b, int &x, int &y) {
	if (b == 0) {
		x = 1, y = 0;
		return a;
	}
	int x1, y1;
	int r = ex_gcd(b, a % b, x1, y1);
	x = y1, y = x1 - a / b * y1;  //对应上面的公式,k=a/b
	return r;

}


int main() {
	int a, b;
	while (cin >> a >> b){
		int x, y;
		int c = ex_gcd(a, b, x, y);
		cout << a << " * " << x << " + " << b << " * " << y << " = " << c << endl;
	}
	return 0;
}

程序输出:

4 6
4 * -1 + 6 * 1 = 2
7 9
7 * 4 + 9 * -3 = 1
6 9
6 * -1 + 9 * 1 = 3

扩展欧几里得算法的用途

求解同余式中系数的值。

例如求解如下的余式:

a x % b = c ax \% b = c ax%b=c

这里的 c c c 不一定是 a a a b b b 的最大公约数,只要其实 a a a b b b 最大公约数 的倍数即可。

因为根据扩展欧几里得算法,存在 x ′ , y ′ x', y' x,y, 使得
a x ′ + b y ′ = c ′ \begin{align}ax' + by' = c'\end{align} ax+by=c

其中 c ′ = g c d ( a , b ) c' = gcd(a, b) c=gcd(a,b), 且 c = k ′ ∗ c ′ c = k' * c' c=kc

给(4)式两边同乘 k ′ k' k, 即得到

k ′ x ′ ∗ a + k ′ y ′ ∗ a = k ′ ∗ c ′ = c \begin{align}k'x' * a + k'y' * a = k' * c' = c\end{align} kxa+kya=kc=c

而要求的式子 a x % b = c ax\%b=c ax%b=c 可以整理成

a x − k b = c ax - kb = c axkb=c

只需令 x = k ′ x ′ , k = − k ′ y ′ x = k'x', k = -k'y' x=kx,k=ky,即可求得 x 的值。

即 余式
a x % b = c ax\%b=c ax%b=c 中的 x x x 自然必定存在且可求。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/317539.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

PLC数组队列搜索FC(SCL代码+梯形图程序)

根据输入数据搜索输入数据队列中和输入数据相同的数,函数返回其所在队列的位置。这里我们需要用到博途PLC的数组指针功能,有关数组指针的详细使用方法,可以参考下面文章: 博途PLC数组指针: https://rxxw-control.blog.csdn.net/article/details/134761364 区间搜索FC …

软件测试|Git:fatal: refusing to merge unrelated histories错误分析与解决

问题介绍 在使用Git时&#xff0c;有时我们可能会遇到以下错误消息&#xff1a; fatal: refusing to merge unrelated histories这个错误通常发生在尝试合并两个不相关的Git仓库历史时。在本文中&#xff0c;我们将详细解释为什么会出现这个错误以及如何解决它。 问题分析 …

代码随想录算法训练营第四天 | 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II

代码随想录算法训练营第四天 | 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II 文章目录 代码随想录算法训练营第四天 | 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II1 Le…

CSS样式学习

html超文本传输标签&#xff0c;属性等权重 outline 标签轮廓 <input type"text"> <textarea cols"30" rows"10"></textarea> outline: none; 表示无轮廓 &#xff08;开发时用的比较多&#xff09; CSS 轮廓&#xff…

大创项目推荐 深度学习疫情社交安全距离检测算法 - python opencv cnn

文章目录 0 前言1 课题背景2 实现效果3 相关技术3.1 YOLOV43.2 基于 DeepSort 算法的行人跟踪 4 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; **基于深度学习疫情社交安全距离检测算法 ** 该项目较为新颖&#xff0c;适合作为竞赛…

【踩坑】flask_uploads报错cannot import name ‘secure_filename‘

转载请注明出处&#xff1a;小锋学长生活大爆炸[xfxuezhang.cn] 背景说明 截至目前&#xff0c;用新版的flask实现文件上传(用到flask_uploads库)&#xff0c;会出现这个问题。 问题原因 版本问题&#xff0c;新的werkzeug已经把secure_filename的位置改了。 解决方法 手动修改…

第23集《佛法修学概要》

庚二、不偷盗分五&#xff1a;辛一、解释名义&#xff1b;辛二、具缘成犯&#xff1b;辛三、犯戒轻重&#xff1b;辛四、开缘情况&#xff1b;辛五、持犯得失 请大家打开讲义第六十五页。我们看庚二、不偷盗。 这一科&#xff0c;我们讲到人天乘的法门。五戒十善为什么叫人天…

【数模百科】距离美赛还有20天,不要忘了阅读往年获奖论文(附04-23年美赛获奖论文)

之前发了很多数模相关的知识&#xff0c;受到了一些人的关注&#xff0c;也有很多人私下问我&#xff0c;距离美赛还有20几天了&#xff0c;还来不来得及。 对此我想说&#xff0c; 来不来得及重要吗&#xff1f; 你名都报了&#xff0c;钱也交了&#xff0c;还是笔不小的钱…

OpenGL 网格拾取坐标(Qt)

文章目录 一、简介二、代码实现三、实现效果参考资料一、简介 有时候我们希望通过鼠标来拾取某个网格中的坐标,这就涉及到一个很有趣的场景:光线投射,也就是求取一条射线与网格的交点,这里如果我们采用普通遍历网格中的每个面片的方式,当网格的面片数据量很大时计算效率就…

H7303 无电感,线性恒流,低压差,大电流,车灯/台灯 9V 12V 24V 30V

线性恒流芯片是一种用于控制电流的电子元件&#xff0c;通常用于驱动LED等器件。它的工作原理是通过维持输出电流的恒定来保持被驱动器件的亮度或功率稳定。 具体来说&#xff0c;线性恒流芯片会监测输出电流并调整电压以保持恒定的电流流过被驱动器件。以下是其基本工作步骤&…

国内镜像:极速下载编译WebRTC源码(For Android/Linux/IOS)(二十四)

简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 优质专栏:多媒体系统工程师系列【原创干货持续更新中……】🚀 人生格言: 人生从来没有捷径,只…

基础数据结构第九期 堆(数组+STL)

前言 堆是一种重要的数据结构&#xff0c;因此应该熟练掌握。 一、堆的基本概念 堆的基本&#xff1a; 堆的结构实际上是一棵完全二叉树&#xff0c;堆可以分为大根堆和小根堆 大根堆&#xff1a; 小根堆&#xff1a; 堆的储存&#xff1a; 若节点小标为i&#xff0c;则左子…

常用计算电磁学算法特性与电磁软件分析

常用计算电磁学算法特性与电磁软件分析 参考网站&#xff1a; 计算电磁学三大数值算法FDTD、FEM、MOM ADS、HFSS、CST 优缺点和应用范围详细教程 ## 基于时域有限差分法的FDTD的计算电磁学算法&#xff08;含Matlab代码&#xff09;-框架介绍 参考书籍&#xff1a;The finite…

three.js 学习笔记(学习中1.10更新) |

文章目录 three.js 学习笔记基础概念透视相机 第一个three.js应用threejs画布尺寸和布局canvas画布宽高度动态变化 坐标辅助器 THREE.AxesHelper实现动画效果requestAnimationFrame时间相关属性和方法 THREE.Clock类 相机控件 轨道控制器OrbitControls 灯光点光源点光源辅助观察…

基于python舆情分析可视化系统+情感分析+爬虫+机器学习(源码)✅

大数据毕业设计&#xff1a;Python招聘数据采集分析可视化系统✅ 毕业设计&#xff1a;2023-2024年计算机专业毕业设计选题汇总&#xff08;建议收藏&#xff09; 毕业设计&#xff1a;2023-2024年最新最全计算机专业毕设选题推荐汇总 &#x1f345;感兴趣的可以先收藏起来&…

怎么安装IK分词器

.安装IK分词器 1.在线安装ik插件&#xff08;较慢&#xff09; # 进入容器内部 docker exec -it elasticsearch /bin/bash ​ # 在线下载并安装 ./bin/elasticsearch-plugin install https://github.com/medcl/elasticsearch-analysis-ik/releases/download/v7.12.1/elastics…

4.4 千万 TOKEN 心理咨询语料库发布,专为大模型,让人工智能技术更好的服务人

2023 年&#xff0c;全网火爆聊天机器人&#xff0c;不同行业企业开始探索应用大模型于垂直领域&#xff0c;当算法和算力已经被证明是行之有效的&#xff0c;那么重头戏就是数据了&#xff0c;Chatopera 近日发布了心理咨询行业的又一大规模语料 - 包含 4.4 千万 TOKEN 的多轮…

设计模式之策略模式【行为型模式】

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档> 学习的最大理由是想摆脱平庸&#xff0c;早一天就多一份人生的精彩&#xff1b;迟一天就多一天平庸的困扰。各位小伙伴&#xff0c;如果您&#xff1a; 想系统/深入学习某…

反爬虫策略:使用FastAPI限制接口访问速率

目录 引言 一、网络爬虫的威胁 二、FastAPI 简介 三、反爬虫策略 四、具体实现 五、其他反爬虫策略 六、总结 引言 在当今的数字时代&#xff0c;数据已经成为了一种宝贵的资源。无论是商业决策、科学研究还是日常生活&#xff0c;我们都需要从大量的数据中获取有价值的…

【JaveWeb教程】(25) JDBC、数据库连接池、Lombok 详细代码示例讲解(最全面)

目录 2. JDBC介绍(了解)2.1 介绍2.2 代码2.3 问题分析2.4 技术对比 3. 数据库连接池3.1 介绍3.2 产品 4. lombok4.1 介绍4.2 使用 2. JDBC介绍(了解) 2.1 介绍 通过Mybatis的快速入门&#xff0c;我们明白了&#xff0c;通过Mybatis可以很方便的进行数据库的访问操作。但是大…