AcWing算法提高课-5.6.1同余方程
宣传一下 算法提高课整理
CSDN个人主页：更好的阅读体验
原题链接
题目描述
求关于 x x x 的同余方程 a x ≡ 1 ( m o d b ) ax ≡ 1 \pmod b ax≡1(modb) 的最小正整数解。
输入格式
输入只有一行，包含两个正整数 a , b a,b a,b，用一个空格隔开。
输出格式
输出只有一行，包含一个正整数 x x x，表示最小正整数解。
输入数据保证一定有解。
数据范围
2 ≤ a , b ≤ 2 × 1 0 9 2 \le a,b \le 2 \times 10^9 2≤a,b≤2×109
输入样例：
3 10
输出样例：
7
思路
我们对 a x ≡ 1 ( m o d b ) ax ≡ 1 \pmod b ax≡1(modb) 进行变形：
设 y ∈ R y \in \mathbb{R} y∈R，则：
a x ≡ 1 ( m o d b ) ⇔ a x − b y = 1 ax \equiv1 \pmod b \Leftrightarrow ax-by=1 ax≡1(modb)⇔ax−by=1
我们知道，扩展欧几里得算法可以计算形如 a x + b y = gcd ( a , b ) ax+by=\gcd(a,b) ax+by=gcd(a,b) 的方程的解。
所以直接进行转化即可。
注意： 由于题目要求输出正整数解，所以我们输出 ( x m o d p + p ) m o d p (x \bmod p + p) \bmod p (xmodp+p)modp 即可。
算法时间复杂度 O ( log n ) O(\log n) O(logn)
AC Code
C + + \text{C}++ C++
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;LL exgcd(LL a, LL b, LL &x, LL &y)
{if (!b){x = 1, y = 0;return a;}LL d = exgcd(b, a % b, y, x);y -= a / b * x;return d;
}int main()
{LL a, b, x, y;cin >> a >> b;exgcd(a, b, x, y);cout << (x % b + b) % b << endl;return 0;
}
最后，如果觉得对您有帮助的话，点个赞再走吧！