AcWing算法提高课-5.6.1同余方程

宣传一下 算法提高课整理

CSDN个人主页：更好的阅读体验

原题链接

题目描述

求关于 $x$ 的同余方程 $ax\equiv 1(\mathrm{mod}b)$ 的最小正整数解。

输入格式

输入只有一行，包含两个正整数 $a,b$，用一个空格隔开。

输出格式

输出只有一行，包含一个正整数 $x$，表示最小正整数解。

输入数据保证一定有解。

数据范围

$2\le a,b\le 2\times 10^9$

输入样例：

3 10
1

输出样例：

7
1

---

思路

我们对 $ax\equiv 1(\mathrm{mod}b)$ 进行变形：

设 $y\in \mathbb{R}$，则：

$$ax\equiv 1(\mathrm{mod}b)\iff ax-by=1$$

我们知道，扩展欧几里得算法可以计算形如 $ax+by=\gcd (a,b)$ 的方程的解。

所以直接进行转化即可。

注意： 由于题目要求输出正整数解，所以我们输出 $(x\mathrm{mod}p+p)\mathrm{mod}p$ 即可。

算法时间复杂度 $O(\log n)$

AC Code

$\text{C}++$

#include 
#include 
#include 

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

最后，如果觉得对您有帮助的话，点个赞再走吧！