1.定义

逆元素，是指一个可以取消另一给定元素运算的元素，在数学里，逆元素广义化了加法中的加法逆元和乘法中的倒数。

如果说 a 在模 p 意义下的乘法逆元是 x，那么 ax≡1(modp)

2.求逆元的方法

·扩展欧几里得

1. 同余方程的转化

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;
}