逆元

文章转载自算法学习笔记(9):逆元 - 知乎 (zhihu.com),如有侵权,请联系作者删除。


逆元的引入

在数论中,如果ab1(mod p),我们就说ab在模p意义下互为乘法逆元,记作a=inv(b)

为什么要引入逆元?常常会遇到一些题目要求结果对一个大质数p取模,这是因为答案很大,出题人为了不麻烦大家写高精,就采取这样的方法。加减法乘法对取模运算都是封闭的,所以你可以处处取模来避免溢出。

但是遇到除法时,就麻烦了:

为了解决模意义下的除法问题,我们引入了逆元。inv(a)其实可以看作是模p意义下的1a,那么在模p意义下,ab就可以变成ainv(b)(mod p)

实际上,在模10意义下的inv(3)=7,所以上面的式子可以这样计算:

这里介绍三种计算逆元的方法:拓展欧几里得费马小定理线性递推


拓展欧几里得

最常用的求逆元方法,代码如下:

ll exgcd(ll a, ll b, ll &x, ll &y)// 拓欧
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
ll inv(ll a, ll p)
{
ll x, y;
if (exgcd(a, p, x, y) != 1) // 无解的情形
return -1;
return (x % p + p) % p;
}

费马小定理

费马小定理叙述如下:

p是质数,且gcd(a,p)=1,则有ap11(mod p)

从逆元的定义可以推导:ainv(a)ap1(mod p),于是有inv(a)ap2(mod p)

于是对ap2算一下快速幂即可。注意:这个方法的前提是:p是质数。

inline ll qpow(ll a, ll n, ll p)// 快速幂
{
ll ans = 1;
while (n)
{
if (n & 1)
ans = ans % p * a % p;
a = a % p * a % p;
n >>= 1;
}
return ans;
}
inline ll inv(ll a, ll p)
{
return qpow(a, p - 2, p);
}

线性递推

以上两种方法都是常用的求逆元方法,但是,洛谷上的这道毒瘤模板题,必须要用特殊的方法:

洛谷P3811 【模板】乘法逆元

题目背景 这是一道模板题 题目描述 给定np ,求 1n中所有整数在模p意义下的乘法逆元。 输入格式 一行两个正整数n,p输出格式 输出n行,第i行表示i在模p下的乘法逆元。

因为这道题要求一系列的乘法逆元,而且数据范围是1n106 ,常规方法是行不通的。这里介绍逆元的线性递推求法(需保证p是质数)。

p=aq+r,即q=p/ar=p mod a

在模p意义下,有aq+r0 (mod p)

整理可得:a=rinv(q) (mod p)

那么inv(a)=qinv(r) (mod p)

即:inv(a)=p/ainv(p mod a) (mod p)

其实和拓展欧几里得还是有不少相似之处的。我们可以用记忆化搜索的方法,减少多次查询的时间复杂度(空间换时间)。(递推亦可,其实就这题而言递推更好)

// 多次对不同的p使用需要清空Inv数组
ll Inv[MAXN] = {0, 1};
inline ll mod(ll a, ll p)
{
return (a % p + p) % p;
}
ll inv(ll a, ll p)
{
if (Inv[a])
return Inv[a];
Inv[a] = mod(-p / a * inv(p % a, p), p);
return Inv[a];
}

自己的实现

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=3e6+10;
ll inv[N];
int main(){
int n,p;
cin>>n>>p;
inv[1]=1;
for(int i=2;i<=n;i++){
inv[i]=(p-p/i)*inv[p%i]%p;
}
for(int i=1;i<=n;i++){
cout<<inv[i]<<"\n";
}
return 0;
}