同余方程
同余方程
题意描述
求关于 的同余方程
的最小正整数解，若无解，输出"-1"
思路
实际上就是求a的逆元 有这样几种方法
- 费马小定理
- 解不定方程
- 欧拉定理
, 那么
一定是a的逆元 但是费马小定理和欧拉定理求出来的不一定是最小的正整数解，所以我们考虑用"解不定方程"
解不定方程
可以转换为
, 求解
就好了
- 但是求出来的只是其中一组解，我们要求出来最小的那一组才行
- 假设求出来的一组解是
， 那通解就是
,
- 要求最小的
,为了方便，让
， 那么
- 代回去，
, 发现这个东西不就是
%
吗
代码
#include <bits/stdc++.h>
#define endl '\n'
using lli = long long;
lli exgcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
lli r = exgcd(b, a % b, x, y);
std::tie(x, y) = std::make_tuple(y, x - (a / b) * y);
return r;
}
int main()
{
int a = 0, b = 0, x = 0, y = 0;
std::cin >> a >> b;
lli r = exgcd(a, b, x, y);
if (r != 1)
{
std::cout << -1 << endl;
}
else
{
int tmp = abs(a / r);
std::cout << (x % tmp + tmp) % tmp << endl;
}
return 0;
}
兄弟我和你说我好几次三面挂了会让你心情好一点嘛
腾讯HR面1365人在聊
查看21道真题和解析
