乘法逆元笔记(蒙哥马利快速幂模)

定义

何为逆元？逆元，又称数论倒数。若整数a、b满足同余方程a*b=1(mod n)，那么a，b互为模n意义下的逆元。

前置 \(1\) ：快速幂

给你三个整数 \(a,b,p\)，求 \(a^b \bmod p\)。
如果直接算复杂度太高了，我们优化。
基本的快速幂公式
\(a^b\) 有两种情况，一种是 \(n\) 为偶数，一种是 \(n\) 为奇数。
因为 \(a^{m+n}=a^m+a^n\).
所以当 \(n\) 为偶数时 \(a^n=a^{n/2}*a^{n/2}\) ，而当 \(n\) 为奇数时，则在此基础上再多乘上一个 \(a\) 就可以了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a,b,p;
int qmi(int a,int b,int p){
	int x=1;
	while(b){
		if(b&1) x=x*a%p;
		a=a*a%p;
		b/=2;
	}
	return x;
}
signed main(){
	cin>>a>>b>>p;
	printf("%lld^%lld mod %lld=%lld\n",a,b,p,qmi(a,b,p));
	return 0;
}

前置 \(2\) ：费马小定理

先来讲讲费马小定理(知道怎么用就好,不用推的)。
这是费马小定理的原始状态: \(a^p ≡ a (mod\ p)\) ,其中 \(a\) , \(p\) 互质。然后, 原式 => $a^p - a ≡0 (mod\ p) $=> \(a*(a^{p-1} - 1) ≡0 (mod\ p)\)=> \(a^{p-1}-1 ≡0 (mod\ p)\) => \(a^{p-1} ≡1 (mod\ p)\)。
这就是费马小定理的结论,求逆元时常用的。

蒙哥马利快速幂模

这个方法的的局限性很大,只有在 \(p\) 是质数的情况下才可以使用。
设 \(inv(a)\) 是 \(a\) 的逆元 由定义得, \(inv(a) * a ≡1 (mod\ p)\) 。
又有费马小定理 \(a^{p-1} ≡1\) , 易得 \(inv(a) * a ≡a^{p-1} (mod\ p)\) 。
移项,得: \(inv(a) ≡ a^{p-2}\) 。
然后这就是蒙哥马利快速幂模算法的一个前提条件: \(inv(a) ≡ a^{p-2} (mod\ p)\) 。

#include<bits/stdc++.h>
using namespace std;
int a,b,p;
int qmi(int a,int b,int p){
	int x=1;
	while(b){
		if(b&1) x=x*a%p;
		a=a*a%p;
		b>>=1;
	}
	return x;
}
int main(){
	cin>>a>>p;
	cout<<qmi(a,p-2,p)<<endl;
	return 0;
}

OK,完结撒花。