东灯的寒舍

你特别好，我喜欢你

0%

逆元

Posted on Edited on In

Native

若 $a × x \equiv 1(mod \ b)$，$a，b$ 互质，则称 $x$ 为 $a$ 的逆元，记为 $a^{-1}$。

逆元用于计算 $t/a \ mod \ b$ 时，转化为 $t×a^{-1} \ mod \ b$。

求逆元

拓展欧几里德

有一个在线性同余方程部分没有记录的性质：

然后就可以根据 $a×x\equiv1(mod \ b)$ 得出

然后用拓展欧几里德解该方程即可。

1
2
3
4
5
6
7
8
9
10
void exgcd(int a,int b,int &x,int &y){
	if(!b){x=1,y=0;return;}
	exgcd(b,a%b,x,y);
	int temp=x;x=y;y=temp-(a/b)*y;
}
int exgcd_inv(int a,int mod){
    int x,y;
    exgcd(a,mod,x,y);
    return gcd(a,mod)==1?(x+mod)%mod:-1;
}
费马小定理

考虑通过费马小定理，如果$b$是质数的情况下：

因此用快速幂求出 $a^{b-2}$ 即可，与 $a$ 相乘正好是 $a^{b-1}$。

但是因为费马小定理必须规定 $b$ 为质数，因此该推论只能用于 $b$ 是质数的情况。

1
2
3
4
5
6
7
8
9
10
inline int fastpow(int a,int b,int m){
	int re=1,t=a;
	while(b){
		if(b&1)re=re*t%m; 
		t=t*t%m;
		b>>=1;
	}
	return re;
}
#define fermat_inv(a,mod) fastpow(a,mod-2,mod)
线性递推逆元

有一种线性的逆元递推方法，证明和实现都非常显然。

1
2
3
4
5
6
7
#define MAXN 3000005
int inv[MAXN];
void GetInv(int n,int p){
    inv[1]=1;
    for(int i=2;i<=n;++i)
        inv[i]=(long long)(p-p/i)*inv[p%i]%p;
}

总结对比

算法名称 复杂度 前提 特点
拓展欧几里德 $O(log_2(a+b))$ $ab$ 互质 $b$ 可以为合数
费马小定理 $O(log_2b)$ $ab$ 互质 $b$ 必须为质数
线性递推 $O(N)$ - -