热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

gcdexgcd斐蜀定理的求解方法及应用

本文介绍了求解gcdexgcd斐蜀定理的迭代法和递归法,并解释了exgcd的概念和应用。exgcd是指对于不完全为0的非负整数a和b,gcd(a,b)表示a和b的最大公约数,必然存在整数对x和y,使得gcd(a,b)=ax+by。此外,本文还给出了相应的代码示例。

gcd就是求a和b最大公约数,一般方法就是递推。不多说,上代码。

一.迭代法

int gcd(int m, int n)
{
while(m>0) { int c = n % m; n = m; m = c; } return n;
}

二.递归法

int Gcd(int a, int b)
{
if(b == 0)return a;return Gcd(b, a % b);
}

但exgcd是个什么玩意???

百度了一下,百科这么讲的:

对于不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,必然

存在整数对 x,y ,使得 gcd(a,b)=ax+by。

好像很好理解的样子,百度还给了个代码

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

???什么玩意???

于是我又找了一段证明:

证明:当 b=0 时,gcd(a,b)=a,此时 x=1 , y=0当 b!=0 时,设 ax1+by1=gcd(a,b)=gcd(b,a%b)=bx2+(a%b)y2又因 a%b=a-a/b*b则 ax1+by1=bx2+(a-a/b*b)y2ax1+by1=bx2+ay2-a/b*by2ax1+by1=ay2+bx2-b*a/b*y2ax1+by1=ay2+b(x2-a/b*y2)解得 x1=y2 , y1=x2-a/b*y2因为当 b=0 时存在 x , y 为最后一组解而每一组的解可根据后一组得到所以第一组的解 x , y 必然存在得证

 于是刚才那段代码返回的是a和b的gcd

void exgcd(int a,int b)
{
if (b){exgcd(b,a%b);int k=x;x=y;y=k-a/b*y; //k就是上一组的x-- y1 = x2 - a/b*y2;}else y=(x=1)-1;
}

还有一个斐蜀定理。。。

若a,b是整数,且(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立。

它的一个重要推论是:a,b互质的充要条件是存在整数x,y使ax+by=1.

转:https://www.cnblogs.com/DukeLv/p/8406940.html



推荐阅读
  • 微软头条实习生分享深度学习自学指南
    本文介绍了一位微软头条实习生自学深度学习的经验分享,包括学习资源推荐、重要基础知识的学习要点等。作者强调了学好Python和数学基础的重要性,并提供了一些建议。 ... [详细]
  • 本文介绍了在开发Android新闻App时,搭建本地服务器的步骤。通过使用XAMPP软件,可以一键式搭建起开发环境,包括Apache、MySQL、PHP、PERL。在本地服务器上新建数据库和表,并设置相应的属性。最后,给出了创建new表的SQL语句。这个教程适合初学者参考。 ... [详细]
  • 本文介绍了数据库的存储结构及其重要性,强调了关系数据库范例中将逻辑存储与物理存储分开的必要性。通过逻辑结构和物理结构的分离,可以实现对物理存储的重新组织和数据库的迁移,而应用程序不会察觉到任何更改。文章还展示了Oracle数据库的逻辑结构和物理结构,并介绍了表空间的概念和作用。 ... [详细]
  • 本文介绍了一些好用的搜索引擎的替代品,包括网盘搜索工具、百度网盘搜索引擎等。同时还介绍了一些笑话大全、GIF笑话图片、动态图等资源的搜索引擎。此外,还推荐了一些迅雷快传搜索和360云盘资源搜索的网盘搜索引擎。 ... [详细]
  • SpringMVC接收请求参数的方式总结
    本文总结了在SpringMVC开发中处理控制器参数的各种方式,包括处理使用@RequestParam注解的参数、MultipartFile类型参数和Simple类型参数的RequestParamMethodArgumentResolver,处理@RequestBody注解的参数的RequestResponseBodyMethodProcessor,以及PathVariableMapMethodArgumentResol等子类。 ... [详细]
  • Skywalking系列博客1安装单机版 Skywalking的快速安装方法
    本文介绍了如何快速安装单机版的Skywalking,包括下载、环境需求和端口检查等步骤。同时提供了百度盘下载地址和查询端口是否被占用的命令。 ... [详细]
  • 在Docker中,将主机目录挂载到容器中作为volume使用时,常常会遇到文件权限问题。这是因为容器内外的UID不同所导致的。本文介绍了解决这个问题的方法,包括使用gosu和suexec工具以及在Dockerfile中配置volume的权限。通过这些方法,可以避免在使用Docker时出现无写权限的情况。 ... [详细]
  • Lodop中特殊符号打印设计和预览样式不同的问题解析
    本文主要解析了在Lodop中使用特殊符号打印设计和预览样式不同的问题。由于调用的本机ie引擎版本可能不同,导致在不同浏览器下样式解析不同。同时,未指定文字字体和样式设置也会导致打印设计和预览的差异。文章提出了通过指定具体字体和样式来解决问题的方法,并强调了以打印预览和虚拟打印机测试为准。 ... [详细]
  • Final关键字的含义及用法详解
    本文详细介绍了Java中final关键字的含义和用法。final关键字可以修饰非抽象类、非抽象类成员方法和变量。final类不能被继承,final类中的方法默认是final的。final方法不能被子类的方法覆盖,但可以被继承。final成员变量表示常量,只能被赋值一次,赋值后值不再改变。文章还讨论了final类和final方法的应用场景,以及使用final方法的两个原因:锁定方法防止修改和提高执行效率。 ... [详细]
  • GetWindowLong函数
    今天在看一个代码里头写了GetWindowLong(hwnd,0),我当时就有点费解,靠,上网搜索函数原型说明,死活找不到第 ... [详细]
  • EPICS Archiver Appliance存储waveform记录的尝试及资源需求分析
    本文介绍了EPICS Archiver Appliance存储waveform记录的尝试过程,并分析了其所需的资源容量。通过解决错误提示和调整内存大小,成功存储了波形数据。然后,讨论了储存环逐束团信号的意义,以及通过记录多圈的束团信号进行参数分析的可能性。波形数据的存储需求巨大,每天需要近250G,一年需要90T。然而,储存环逐束团信号具有重要意义,可以揭示出每个束团的纵向振荡频率和模式。 ... [详细]
  • 电销机器人作为一种人工智能技术载体,可以帮助企业提升电销效率并节省人工成本。然而,电销机器人市场缺乏统一的市场准入标准,产品品质良莠不齐。创业者在代理或购买电销机器人时应注意谨防用录音冒充真人语音通话以及宣传技术与实际效果不符的情况。选择电销机器人时需要考察公司资质和产品品质,尤其要关注语音识别率。 ... [详细]
  • HDU 2372 El Dorado(DP)的最长上升子序列长度求解方法
    本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法,通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]
  • 缤果串口网络蓝牙调试助手的特点和下载链接
    本文介绍了缤果串口网络蓝牙调试助手的主要特点,包括支持常用的波特率、校验、数据位和停止位设置,以及以ASCII码或十六进制接收或发送数据或字符的功能。该助手还能任意设定自动发送周期,并能将接收数据保存成文本文件。同时,该软件支持网络UDP/TCP和蓝牙功能。最后,提供了腾讯微云和百度网盘的下载链接。 ... [详细]
  • 本文介绍了C++中的引用运算符及其应用。引用运算符是一种将变量定义为另一个变量的引用变量的方式,在改变其中一个变量时,两者均会同步变化。引用变量来源于数学,在计算机语言中用于储存计算结果或表示值抽象概念。变量可以通过变量名访问,在指令式语言中引用变量通常是可变的,但在纯函数式语言中可能是不可变的。本文还介绍了引用变量的示例及验证,以及引用变量在函数形参中的应用。当定义的函数使用引用型形参时,函数调用时形参的改变会同时带来实参的改变。 ... [详细]
author-avatar
飞翔1
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有