对于同余方程的话就是一个经典扩展欧几里得求逆元的题目。
这个可以转换成,我们需要求的只是x和k从而得到一组解。
通常我们会得到a和b两个元素,假设a是7,b为40,通过扩展欧几里得进行运算。
这时也就是,我们第一步先开始从a,b两个数字里找到最大的那个
在这里的话是40,然后利用大的去除以小的也就是,5乘7得35,40-35余5。
- ①
,这个为我们的式子①号,我们先放一边。
然后这时,我们要用余数和7去进行比较谁大,这里是7大,所以用大的去除以小的也就是
- ②
,这个为我们的式子②号,因为我们的余数还未得到1,则继续此操作。
此时2与5去相比则为,余数为1了,那么写完最后一个式子就可以开始代换了。
- ③
这个为我们最后的式子,因为已经得到1了,现在开始合并同类项
我们通过上面式子②替换掉式子中的2代入式子3中
- ④
此时我们的新式子还一个5,那么代入式子①进入
这里的话我们用式子①将式子④中的5替换掉
- ⑤
这时候进行合并同类项
⑤此时式子中还含有5这个元素我们继续使用式子①进行代换(将式子中所有元素代换为ax-by=1即可)
- ⑥
然后进行合并同类项
⑥ 那么此时带入原式
中则:
- 由于是负数,我们要将其化为正数,直接利用
则结果为23
以上为扩展欧几里得数学演示。
下面为题目以及代码实现扩展欧几里得。
洛谷题目:P1082同余方程
输入:
输出:
#include <bits/stdc++.h>
#define simeple freopen("input", "r", stdin),freopen("output", "w", stdout);
#define fast ios::sync_with_stdio(false),cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// 扩展欧几里得算法函数,计算 ax + by = gcd(a, b) 的解 (x, y) 和 gcd(a, b)
int exgcd(int a, int b, int &x, int &y) {
if (!b) { // 如果 b 为 0,意味着 gcd(a, b) = a,此时 x = 1, y = 0
x = 1;
y = 0;
return a;
}
// 递归调用,直到 b 为 0
int d = exgcd(b, a % b, x, y);
int t = x; // 保存当前 x 的值
x = y; // 更新 x 的值为上一步 y 的值
// 更新 y 的值为 t - (a / b) * y, 其中 t 是上一步的 x
y = t - (a / b) * y;
return d; // 返回 gcd(a, b)
}
// 用于求解模逆元,返回 a 在模 b 意义下的逆元,即 x 使得 ax ≡ 1 (mod b)
int Exgcd(int a, int b) {
int x, y; // 用于存储扩展欧几里得算法的解
int gcd = exgcd(a, b, x, y); // 计算 gcd(a, b) 及对应的 x, y
// 返回 x 在模 b 意义下的正整数形式的逆元
return (x % b + b) % b;
}
int main()
{
fast
//simeple
int a, b;
cin >> a >> b;
cout << Exgcd(a, b);
return 0;
}
标签:gcd,int,逆元,欧几里得,long,详解,同余,式子
From: https://blog.csdn.net/m0_73147661/article/details/140275900