扩展欧几里得算法
2022/3/8 22:44:38
本文主要是介绍扩展欧几里得算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
扩展欧几里得算法
用途:给定 n 对正整数 ai,bi,对于每对数,求出一组 xi,yi,使其满足 ai×xi+bi×yi=gcd(ai,bi)。
应用: 求解一次同余方程 ax≡b(modm)则等价于求ax=m∗(−y)+b ax+my=b
有解条件为 gcd(a,m)|b,然后用扩展欧几里得求解即可
特别的 当 b=1 且 a与m互质时 则所求的x即为a的逆元
1 #include <bits/stdc++.h> 2 using namespace std; 3 int n; 4 int exgcd(int a,int b,int &x,int &y) 5 { 6 if(b==0) 7 { 8 x=1,y=0; 9 return a; 10 } 11 int x1,y1,gcd; 12 gcd=exgcd(b,a%b,x1,y1); 13 x=y1,y=x1-a/b*y1; 14 return gcd; 15 } 16 int main() 17 { 18 int x,y; 19 scanf("%d",&n); 20 for(int i=1;i<=n;i++) 21 { 22 int a,b; 23 scanf("%d%d",&a,&b); 24 exgcd(a,b,x,y); 25 printf("%d %d\n",x,y); 26 27 } 28 return 0; 29 }
这篇关于扩展欧几里得算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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