逆元定义：模m意义下，数a如果有逆元x，那么除以a相当于乘以x

即 ($b\times a$)%m = $\left(b\times m\right)% m$%m 称x为a的逆 .还有一个要求 a和m 互质且非负

给定模数m，求a的逆相当于 $ax\equiv1{(mod,m)}$

即 ax - my = 1 实际上线性不定方程无穷多解，这里只求正的最小逆元

a, m要求非负，且 Gcd(a, m) = 1 即a, m互质

逆元求解：

1）扩展欧几里得

2）费马小定理

3）线性求解

扩展欧几里得定理：

已知a,b求解一组x,y 满足 ax + by = Gcd(a, b). 并且已知该方程一定有解

而逆元求 ax - my = 1 即要 Gcd(a,m) = 1 且 a,m非负

ll Extend_Eculid(ll a, ll b, ll &x, ll &y)
{
	if(!b)
	{
		*x = 1; *y = 0;
		return a;
	}
	else
	{
		ll temp = Extend_Eculid(b, a%b, y, x);
		y = y - a/b*x;
		return temp;
	}
}

得到返回值d 要判断一下

int main()
{
	ll a, m, x, y, d ;
	cin>>a>>m;
	d = Extend_Eculid(a, m, &x, &y);	//扩欧定理,返回Gcd(a, m) 
	cout<< (d == 1? (x%m+m)%m : -1)<< endl;	//可能x%m为负,所以再加上m
	return 0;
}

费马小定理：

若p为素数，a为正整数，且a、p互质.则有 $a^{p-1} = 1(mod,,p)$

那么 $a\times a^{p-2} = 1(mod,,p)$

这样a的逆元的解即 $ x = a^{p-2}$ ,使用快速幂求解 $a^{p-2}$ 即可

ll mod_pow(ll x, ll n, ll p)	//代入 a, m-2, m
{
	ll res = 1;
	while(n)
	{
		if(n&1)
			res = res*x%p;
		x = x*x%p;
		n>>=1;	
	}
	return res;
}