(扩展)欧几里得算法、裴蜀定理(贝祖定理)
2021/9/20 20:56:52
本文主要是介绍(扩展)欧几里得算法、裴蜀定理(贝祖定理),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接
acwing3642. 最大公约数和最小公倍数
acwing877. 扩展欧几里得算法
P4549 【模板】裴蜀定理
裴蜀定理:
- 对于任意整数 \(a,b\),存在一对整数 \(x,y\), 满足
ax+by=gcd(a,b)
- \(ax+by=c,x∈Z^∗ ,y∈Z^ ∗\) 成立的充要条件是\({\gcd(a,b)|c}\)。\(Z^*\)表示正整数集。
[acwing3642. 最大公约数和最小公倍数
题目描述
输入两个正整数 \(m\) 和 \(n\),求其最大公约数和最小公倍数。
输入格式
一行,两个整数 \(m\) 和 \(n\)。
输出格式
一行,输出两个数的最大公约数和最小公倍数。
数据范围
\(1≤n,m≤10000\)
输入样例:
5 7
输出样例:
1 35
代码
- 时间复杂度:\(O(a+b)\)
递归
#include<bits/stdc++.h> using namespace std; int gcd(int a,int b) { return b?gcd(b,a%b):a; } int main() { int n,m; scanf("%d%d",&n,&m); printf("%d %d",gcd(n,m),n*m/gcd(n,m)); return 0; }
非递归
#include<bits/stdc++.h> using namespace std; int main() { int n,m; scanf("%d%d",&n,&m); int tmp=n*m; while(m^=n^=m^=n%=m); printf("%d %d",n,tmp/n); return 0; }
acwing877. 扩展欧几里得算法
题目描述
给定 \(n\) 对正整数 \(a_i,b_i\),对于每对数,求出一组 \(x_i,y_i\),使其满足 \(a_i×x_i+b_i×y_i=gcd(a_i,b_i)\)。
输入格式
第一行包含整数 \(n\)。
接下来 \(n\) 行,每行包含两个整数 \(a_i,b_i\)。
输出格式
输出共 \(n\) 行,对于每组 \(a_i,b_i\),求出一组满足条件的 \(x_i,y_i\),每组结果占一行。
本题答案不唯一,输出任意满足条件的 \(x_i,y_i\) 均可。
数据范围
\(1≤n≤10^5, 1≤a_i,b_i≤2×10^9\)
输入样例:
2 4 6 8 18
输出样例:
-1 1 -2 1
代码
- 时间复杂度:\(O(a+b)\)
#include<bits/stdc++.h> using namespace std; int exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1,y=0; return a; } int d=exgcd(b,a%b,x,y); int z=x; x=y,y=z-y*(a/b); return d; } int main() { int t; for(scanf("%d",&t);t;t--) { int a,b,x,y; scanf("%d%d",&a,&b); exgcd(a,b,x,y); printf("%d %d\n",x,y); } return 0; }
[P4549 【模板】裴蜀定理]
题目描述
给定一个包含 \(n\) 个元素的整数序列 \(A\),记作 \(A_1,A_2,A_3,...,A_n\) 。
求另一个包含 \(n\) 个元素的待定整数序列 \(X\),记 \(S=\sum\limits_{i=1}^nA_i\times X_i\),使得 \(S>0\) 且 \(S\) 尽可能的小。
输入格式
第一行一个整数 \(n\),表示序列元素个数。
第二行 \(n\) 个整数,表示序列 \(A\)。
输出格式
一行一个整数,表示 \(S>0\) 的前提下 \(S\) 的最小值。
输入
2 4059 -1782
输出
99
说明/提示
对于 \(100\%\) 的数据,\(1 \le n \le 20\),\(|A_i| \le 10^5\),且 \(A\) 序列不全为 \(0\)。
代码
- 时间复杂度:\(O(\sum{a_i})\)
#include<bits/stdc++.h> using namespace std; int main() { int n,res,other; scanf("%d%d",&n,&res); while(--n) { scanf("%d",&other); res=__gcd(res,other); } printf("%d",abs(res)); return 0; }
这篇关于(扩展)欧几里得算法、裴蜀定理(贝祖定理)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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码农必看:常见源代码混淆技术详解
- 2024-04-07以一当十丨TiDB 在东吴证券秀财 APP 的应用实践
- 2024-04-07月活超 1.1 亿,用户超 4 亿,你也在用的「知乎」是如何在超大规模 TiDB 集群上玩转多云多活的?来听听知乎代晓磊的答案!