[数学]乘法逆元
1.定义
逆元素，是指一个可以取消另一给定元素运算的元素，在数学里，逆元素广义化了加法中的加法逆元和乘法中的倒数。
如果说 a 在模 p 意义下的乘法逆元是 x，那么 ax≡1(modp)
2.求逆元的方法
·扩展欧几里得
- 同余方程的转化
- 扩展欧几里得的求解
代码如下
#include<bits/stdc++.h>
#define int long long
using namespace std;
int x,y;
void exgcd(int a,int b){
//ax+by=gcd(a,b);
if(b==0){
x=1;
y=0;
return;
}
exgcd(b,a%b);
int tmp=x;
x=y;
y=tmp-a/b*y;
}
signed main(){
long a,b;
cin>>a>>b;
exgcd(a,b);
x=(x%b+b)%b;
cout<<x;
return 0;
}