文章目录
前言
一、费蜀定理，扩展欧几里得
二、例题，代码
AcWing 877. 扩展欧几里得算法
本题解析
AC代码
AcWing 878. 线性同余方程
本题解析
AC代码
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解数学知识：扩展欧几里得算法，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、费蜀定理，扩展欧几里得
费蜀定理：对于任意正整数a，b，一定存在非零整数x，y，使得ax + by = gcd(a, b)
扩展欧几里得：求上述的x，y
二、例题，代码
AcWing 877. 扩展欧几里得算法
本题链接：cWing 877. 扩展欧几里得算法
本博客提供本题截图：
本题解析
关于原理，这里不做解释，想要知道的可以面向百度编程，这里提供扩展欧几里得算法模板，该模板来自：ACWing算法基础课
int exgcd(int a, int b, int &x, int &y) { if (!b) { x = 1, y = 0; return a; } int d = exgcd(b, a % b, y, x); y -= a / b * x; return d; }
这里的d还是指的是最大公约数，x和y指的就是题目中需要我们去求的值
AC代码
#include <cstdio> #include <algorithm> using namespace std; int exgcd(int a, int b, int &x, int &y) { if (!b) { x = 1, y = 0; return a; } int d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } int main() { int n; scanf("%d", &n); while (n -- ) { int a, b; scanf("%d%d", &a, &b); int x, y; exgcd(a, b, x, y); printf("%d %d\n", x, y); } return 0; }
AcWing 878. 线性同余方程
本题链接：AcWing 878. 线性同余方程
本博客提供本题截图：
本题解析
这里放一张y总的推导过程图：
可知本题其实还是去用扩展欧几里得算法去求解，只不过本题我们只需要求出来x即可，这里需要知道，只有我们的b是最大公约数gcd(a,m)即d的倍数的时候，这里才能是有解的，即b % d == 0，否则一定是无解的
AC代码
#include <cstdio> #include <algorithm> using namespace std; typedef long long LL; int exgcd(int a, int b, int &x, int &y) { if (!b) { x = 1, y = 0; return a; } int d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } int main() { int n; scanf("%d", &n); while (n -- ) { int a, b, m; scanf("%d%d%d", &a, &b, &m); int x, y; int d = exgcd(a, m, x, y); if (b % d) puts("impossible"); else printf("%d\n", (LL)b / d * x % m); } return 0; }
三、时间复杂度
关于扩展欧几里得算法各步操作的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
