alan23273850 的刷題筆記
a289: Modular Multiplicative Inverse
Tags: m.m.i
出處：https://zerojudge.tw/ShowProblem?problemid=a289
提交：https://zerojudge.tw/Submissions?problemid=a289&account=allllllan123456
問題：給定多組兩個不超過 100,000,000 的正整數 a 和 n，請找出最小的正整數 b 使得 ab $\equiv$ 1 (mod n)，若不存在則輸出 No Inverse。
解法：此乃經典問題，關於解說可參考這裡。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 int a, n;
6 while (cin >> a >> n) {
7 int x1=1, y1=0, x2=0, y2=1;
8 do {
9 int q = (a*x1 + n*y1) / (a*x2 + n*y2);
10 int x3 = x1 - q*x2;
11 int y3 = y1 - q*y2;
12 x1 = x2; y1 = y2; x2 = x3; y2 = y3;
13 } while (a*x2 + n*y2);
14 if (a*x1+n*y1 > 1) cout << "No Inverse\n";
15 else if (n == 1) cout << "No Inverse\n";
16 else cout << (x1 + n) % n << '\n';
17 }
18 return 0;
19}