给出2个数M和N(M < N)，且M与N互质，找出一个数K满足0 < K < N且K * M % N = 1，如果有多个满足条件的，输出最小的。
Solution
用 EXGCD 求解逆元，可以适用于一切 \((M,N)=1\) 的情况
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline void exgcd(int a,int b,int &x,int &y) {
if(!b) {
x=1,y=0;
return;
}
exgcd(b,a%b,x,y);
int t=x;
x=y,y=t-(a/b)*y;
}
inline int inv(int a,int b) {
int x,y;
return exgcd(a,b,x,y),(x%b+b)%b;
}
signed main() {
int n,m;
cin>>m>>n;
cout<<inv(m,n);
}
![【bzoj1009】: [HNOI2008]GT考试 字符串-kmp-矩阵乘法-DP](https://www.kunjuke.com/file/css/thumb/1.jpg/280-180.jpg)
