拓展欧几里得
2022/2/18 23:22:16
本文主要是介绍拓展欧几里得,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
开门见山,直奔主题
首先要了解拓展欧几里得,先要了解几个概念:
一、裴蜀定理
重要推论是:a,b互质的充分必要条件是存在整数x,y使ax+by=1,也就是 ax+by=gcd(a,b)=1
二、乘法逆元
在中国剩余定理的计算里,需要求一个数字在一个模下的逆元,也就是对于给定的 a,b,找到方程 的一个整数解 a* 。接下来我们分析一下这个方程背后隐藏着什么。根据同余的定义,有 ,也就是存在整数 k使得 b*k=aa*-1 。移一下项,就得到了 aa*-bk=1. 即aa*+(-)bk=1这个形式恰好符合裴蜀定理 ax+by=1 的形式,于是 (a,b)=1 ,这表明 a,b互质是逆元存在的必要条件。
三、欧几里得算法
原来博客有提及过,这里就不详写了,给个代码吧
int gcd(int a, int b) { if(a < b) return gcd(b, a); if(b == 0) return a; return gcd(b, a % b); }
呵呵,进入正题
扩展欧几里得计算ax+by=c的整数解(x,y)程序如下:
目前本人还有些不懂,会再问老师。。。
继续水
拜拜
这篇关于拓展欧几里得的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署
- 2024-04-14RAG应用开发实战02-相似性检索的关键 - Embedding
- 2024-04-14出海软件草根逆袭打法是什么?
- 2024-04-13鸿蒙原生应用再新丁!企查查 碧蓝航线 入局鸿蒙
- 2024-04-11RAG应用开发实战(01)-RAG应用框架和解析器
- 2024-04-10DevOps已死?2024年的DevOps将如何发展
- 2024-04-10码农必看:常见源代码混淆技术详解