宣傳一下 算法提高課整理

CSDN個(gè)人主頁(yè)：更好的閱讀體驗(yàn)

原題鏈接

題目描述

求關(guān)于 $x$ 的同余方程 $ax\equiv 1(\mathrm{mod}b)$ 的最小正整數(shù)解。

輸入格式

輸入只有一行，包含兩個(gè)正整數(shù) $a,b$，用一個(gè)空格隔開(kāi)。

輸出格式

輸出只有一行，包含一個(gè)正整數(shù) $x$，表示最小正整數(shù)解。

輸入數(shù)據(jù)保證一定有解。

數(shù)據(jù)范圍

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

輸入樣例：

3 10

輸出樣例：

7

---

思路

我們對(duì) $ax\equiv 1(\mathrm{mod}b)$ 進(jìn)行變形：

設(shè) $y\in \mathbb{R}$，則：

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

我們知道，擴(kuò)展歐幾里得算法可以計(jì)算形如 $ax+by=\gcd (a,b)$ 的方程的解。

所以直接進(jìn)行轉(zhuǎn)化即可。

注意： 由于題目要求輸出正整數(shù)解，所以我們輸出 $(x\mathrm{mod}p+p)\mathrm{mod}p$ 即可。

算法時(shí)間復(fù)雜度 $O(\log n)$

AC Code

$\text{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;
}

---

最后，如果覺(jué)得對(duì)您有幫助的話，點(diǎn)個(gè)贊再走吧！