费马小定理求乘法求逆元

应用条件：当模数p为质数的时候

\(\because ax \equiv 1 \pmod{p}\)

由费马小定理可得：\(ax \equiv a^{p-1} \pmod{p}\)

\(\therefore x \equiv a^{p-2} \pmod{p}\)

至此，我们可以通过快速幂的方法来求乘法逆元了

inline ll inverse(ll a,ll p){
	ll res=1;
	ll b=p-2;
	a=(a%p+p)%p;
	for(;b;b>>=1){
		if(b&1) res=(a*res)%p;
		a=(a*a)%p;
	}
	return res;
}

扩展欧几里得算法求逆元

应用条件：\(gcd(a,b)=1\)

考虑以下a在模p意义下的乘法逆元b的定义： \(a\cdot b \equiv 1 \pmod{p}\)

更一般地，不难想到：\((b_{0} \cdot p+1)\pmod{p} = 1\)

又因为：\((a\cdot b) \mod{p} = 1\)

所以：\(a\cdot b + p\cdot b_{0} =1\)

因此我们可以用扩展欧几里得定理求出以上方程的\(b\)和\(b_{0}\)，其中，b就是a在模p意义下的乘法逆元

void exgcd(int a, int b, int& x, int& y) {
  if (b == 0) {
    x = 1, y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= a / b * x;
}

费马小定理的证明and线性求逆元......