关于 欧几里得算法+裴蜀定理+扩展欧几里得
2022/5/12 20:57:30
本文主要是介绍关于 欧几里得算法+裴蜀定理+扩展欧几里得,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一、欧几里得算法
又称辗转相除法,用于计算两个整数a,b的最大公约数 gcd(a,b)。基本算法:设 a = qb + r,其中a,b,q,r都是整数,则 gcd(a,b) = gcd(b,r),即 gcd(a,b) = gcd(b,a%b)。
证明:
a = qb + r
如果 r = 0,那么 a 是 b 的倍数,此时显然 b 是 a 和 b 的最大公约数。
如果 r ≠ 0,任何整除 a 和 b 的数必定整除 a - qb = r,而且任何同时整除 b 和 r 的数必定整除 qb + r = a,所以 a 和 b 的公约数集合与 b 和r 的公约数集合是相同的。特别的,a 和 b 的最大公约数是相同的。
递归实现:
int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
非递归实现:
int gcd(int a,int b) { while(b!=0) { int r=a%b; a=b; b=r; } return a; }
二、裴蜀定理
又称贝祖等式,是一个关于最大公约数(或最大公约式)的定理。
定理内容:若 a,b 是整数,且 gcd(a,b)=d,那么对于任意的整数 x ,y,ax+by 都一定是 d 的倍数,特别地,一定存在整数 x , y 使 ax+by=d 成立。
简单来说,我们设 d=gcd(a,b) ,那么对于方程 ax+by=d ,一定存在一组整数解。并且对于方程 ax+by=z ,如果满足 d|z ,那么方程一定有整数解,否则无整数解。
证明:
三、扩展欧几里得
看这个吧:https://blog.csdn.net/zhjchengfeng5/article/details/7786595
这篇关于关于 欧几里得算法+裴蜀定理+扩展欧几里得的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署
- 2024-04-14RAG应用开发实战02-相似性检索的关键 - Embedding