乘法逆元小结

• 什么是乘法逆元

当有 $ a*x ≡ 1 \pmod {p} $ 时，则 \(a\)是模 $ p$ 意义下的乘法逆元。

费马小定理求逆元

费马小定理

$a ≡ a^{p-1} \pmod {p} $

所以

$a^{p-2} ≡ 1 \pmod {p} $

求 \(a^{p-2} \bmod p\)即可。

当且仅当 \(p\) 为质数且 \(a,p\) 互质时可用。

int ksm(int x,int k){
	int sum=1;
	while(k){
		if(k&1) sum=sum*x%p;
		x=x*x%p; k>>=1;
	}
	return sum;
}
signed main(){
	px=read(),p=read();
	ans=ksm(x,p-2);
	return 0;
}

扩展欧几里得求逆元

这个方法十分容易理解，而且对于单个查找效率似乎也还不错，比后面要介绍的大部分方法都要快(尤其对于 $ \bmod {p}$比较大的时候)。

这个就是利用拓欧求解 线性同余方程\(a*x≡ c\pmod {b}\)
的$ c=1$的情况。我们就可以转化为解 \(a*x + b*y = 1\) 这个方程。

void Exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) x = 1, y = 0;
    else Exgcd(b, a % b, y, x), y -= a / b * x;
}
int main() {
    ll x, y;
    Exgcd (a, p, x, y);
    x = (x % p + p) % p;
    printf ("%d\n", x); //x是a在mod p下的逆元
}

当 \(a,p\) 互质时即可用。