热门标签 | 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



推荐阅读
  • 本文介绍了在开发Android新闻App时,搭建本地服务器的步骤。通过使用XAMPP软件,可以一键式搭建起开发环境,包括Apache、MySQL、PHP、PERL。在本地服务器上新建数据库和表,并设置相应的属性。最后,给出了创建new表的SQL语句。这个教程适合初学者参考。 ... [详细]
  • 微软头条实习生分享深度学习自学指南
    本文介绍了一位微软头条实习生自学深度学习的经验分享,包括学习资源推荐、重要基础知识的学习要点等。作者强调了学好Python和数学基础的重要性,并提供了一些建议。 ... [详细]
  • 本文介绍了数据库的存储结构及其重要性,强调了关系数据库范例中将逻辑存储与物理存储分开的必要性。通过逻辑结构和物理结构的分离,可以实现对物理存储的重新组织和数据库的迁移,而应用程序不会察觉到任何更改。文章还展示了Oracle数据库的逻辑结构和物理结构,并介绍了表空间的概念和作用。 ... [详细]
  • 本文介绍了九度OnlineJudge中的1002题目“Grading”的解决方法。该题目要求设计一个公平的评分过程,将每个考题分配给3个独立的专家,如果他们的评分不一致,则需要请一位裁判做出最终决定。文章详细描述了评分规则,并给出了解决该问题的程序。 ... [详细]
  • 本文介绍了一些好用的搜索引擎的替代品,包括网盘搜索工具、百度网盘搜索引擎等。同时还介绍了一些笑话大全、GIF笑话图片、动态图等资源的搜索引擎。此外,还推荐了一些迅雷快传搜索和360云盘资源搜索的网盘搜索引擎。 ... [详细]
  • SpringMVC接收请求参数的方式总结
    本文总结了在SpringMVC开发中处理控制器参数的各种方式,包括处理使用@RequestParam注解的参数、MultipartFile类型参数和Simple类型参数的RequestParamMethodArgumentResolver,处理@RequestBody注解的参数的RequestResponseBodyMethodProcessor,以及PathVariableMapMethodArgumentResol等子类。 ... [详细]
  • 阿里Treebased Deep Match(TDM) 学习笔记及技术发展回顾
    本文介绍了阿里Treebased Deep Match(TDM)的学习笔记,同时回顾了工业界技术发展的几代演进。从基于统计的启发式规则方法到基于内积模型的向量检索方法,再到引入复杂深度学习模型的下一代匹配技术。文章详细解释了基于统计的启发式规则方法和基于内积模型的向量检索方法的原理和应用,并介绍了TDM的背景和优势。最后,文章提到了向量距离和基于向量聚类的索引结构对于加速匹配效率的作用。本文对于理解TDM的学习过程和了解匹配技术的发展具有重要意义。 ... [详细]
  • Skywalking系列博客1安装单机版 Skywalking的快速安装方法
    本文介绍了如何快速安装单机版的Skywalking,包括下载、环境需求和端口检查等步骤。同时提供了百度盘下载地址和查询端口是否被占用的命令。 ... [详细]
  • Lodop中特殊符号打印设计和预览样式不同的问题解析
    本文主要解析了在Lodop中使用特殊符号打印设计和预览样式不同的问题。由于调用的本机ie引擎版本可能不同,导致在不同浏览器下样式解析不同。同时,未指定文字字体和样式设置也会导致打印设计和预览的差异。文章提出了通过指定具体字体和样式来解决问题的方法,并强调了以打印预览和虚拟打印机测试为准。 ... [详细]
  • Final关键字的含义及用法详解
    本文详细介绍了Java中final关键字的含义和用法。final关键字可以修饰非抽象类、非抽象类成员方法和变量。final类不能被继承,final类中的方法默认是final的。final方法不能被子类的方法覆盖,但可以被继承。final成员变量表示常量,只能被赋值一次,赋值后值不再改变。文章还讨论了final类和final方法的应用场景,以及使用final方法的两个原因:锁定方法防止修改和提高执行效率。 ... [详细]
  • EPICS Archiver Appliance存储waveform记录的尝试及资源需求分析
    本文介绍了EPICS Archiver Appliance存储waveform记录的尝试过程,并分析了其所需的资源容量。通过解决错误提示和调整内存大小,成功存储了波形数据。然后,讨论了储存环逐束团信号的意义,以及通过记录多圈的束团信号进行参数分析的可能性。波形数据的存储需求巨大,每天需要近250G,一年需要90T。然而,储存环逐束团信号具有重要意义,可以揭示出每个束团的纵向振荡频率和模式。 ... [详细]
  • 本文讨论了如何优化解决hdu 1003 java题目的动态规划方法,通过分析加法规则和最大和的性质,提出了一种优化的思路。具体方法是,当从1加到n为负时,即sum(1,n)sum(n,s),可以继续加法计算。同时,还考虑了两种特殊情况:都是负数的情况和有0的情况。最后,通过使用Scanner类来获取输入数据。 ... [详细]
  • 本文介绍了C++中的引用运算符及其应用。引用运算符是一种将变量定义为另一个变量的引用变量的方式,在改变其中一个变量时,两者均会同步变化。引用变量来源于数学,在计算机语言中用于储存计算结果或表示值抽象概念。变量可以通过变量名访问,在指令式语言中引用变量通常是可变的,但在纯函数式语言中可能是不可变的。本文还介绍了引用变量的示例及验证,以及引用变量在函数形参中的应用。当定义的函数使用引用型形参时,函数调用时形参的改变会同时带来实参的改变。 ... [详细]
  • 本文由编程笔记#小编整理,主要介绍了关于数论相关的知识,包括数论的算法和百度百科的链接。文章还介绍了欧几里得算法、辗转相除法、gcd、lcm和扩展欧几里得算法的使用方法。此外,文章还提到了数论在求解不定方程、模线性方程和乘法逆元方面的应用。摘要长度:184字。 ... [详细]
  • 嵌入式处理器的架构与内核发展历程
    本文主要介绍了嵌入式处理器的架构与内核发展历程,包括不同架构的指令集的变化,以及内核的流水线和结构。通过对ARM架构的分析,可以更好地理解嵌入式处理器的架构与内核的关系。 ... [详细]
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社区 版权所有