扩展欧几里得算法
2022/1/27 22:05:02
本文主要是介绍扩展欧几里得算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 扩展欧几里得算法
- 裴蜀定理
- 欧几里得算法
- 扩展欧几里得算法证明与实现
- 线性同余方程
扩展欧几里得算法
裴蜀定理
ax + by
能够凑出来的最小的值一定是a和b的最大公约数(d的一倍)。
应用:扩展欧几里得算法求系数x
和y
。
欧几里得算法
【代码模板】
LL gcd(LL a, LL b) { if(b == 0) return a; return gcd(b, a % b); }
扩展欧几里得算法证明与实现
设LL exgcd(a,b,x,y)是求解系数x,y的函数,返回值是gcd(a,b),那么可以根据递归求出exacd(b,a%b,i,j)求出系数i,j
根据下面的推导得到x,y与i,j的关系:
【代码模板】
LL exgcd(LL a, LL b, LL &x, LL &y)// 通过引用传回 { if(b == 0) { x = 1, y = 0; return a; } LL d = exgcd(b, a % b, y, x);// 注意:这里换一下顺序y y -= a / b * x; // x = x1 return d; }
【题目链接】877. 扩展欧几里得算法 - AcWing题库
【代码实现】
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; LL exgcd(LL a, LL b, LL &x, LL &y) { if(b == 0) { x = 1, y = 0; return a; } LL d = exgcd(b, a % b, y, x);// 注意:这里换一下顺序y y -= a / b * x; // x = x1 return d; } int main() { int n; scanf("%d", &n); while (n -- ) { LL a, b, x, y; scanf("%lld%lld", &a, &b); exgcd(a, b, x, y); printf("%lld %lld\n", x, y); } return 0; }
线性同余方程
【题目链接】878. 线性同余方程 - AcWing题库
a * x ≡ b (mod m)
----> ax = my + b(y为m的整数倍)
----> ax - my = b,令y1 = -y ----> ax + my1 = b
根据拓展欧几里得定理,只要 b 是 a与m最大公约数的倍数,即b为gcd(a, m)的倍数即有解!反之无解。
若b是最大公约数的倍数,由拓展欧几里得算法可以求出一个系数
x:X1
使得ax + my1 = d
(d为a与m的最大公约数)在有解情况下,由于d与b存在倍数关系,我们可以将ax + my1 = d两边同时扩大
b/d
倍,由于a与m都是定数,也就是说ax + my1 = b
中的x也就是我们题目要求的x会在 上述拓展欧几里得算法求出一个系数x:X1
的基础上乘上b/d
倍。
// 即最后答案为:x=X1 * d / b % m
ax % m=b⟺ a⋅(x % m) % m=b
所以对
x % m
仍是个答案
因为输出要在int范围,所以%m
【代码实现】
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; LL exgcd(LL a, LL b, LL &x, LL &y) { if(b == 0) { x = 1, y = 0; return a; } int d = exgcd(b, a % b, y, x); y -= a/b * x; return d; } // ax % m == b -- > ax = my + b ---> ax + my1 = b int main() { int n; scanf("%d", &n); while (n -- ) { LL a, b, m, x, y; scanf("%lld%lld%lld", &a, &b, &m); LL d = exgcd(a, m, x, y); if(b % d) puts("impossible");//b 不是 d的倍数 则无解 else printf("%lld\n", LL(b/d) * x % m); } return 0; }
学习内容参考:
acwing算法基础课
这篇关于扩展欧几里得算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 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 项目如何部署