逆元

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

逆元的引入

在数论中，如果$ab\equiv1(mod\ p)$，我们就说$a$和$b$在模$p$意义下互为乘法逆元，记作$a=inv(b)$。

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

但是遇到除法时，就麻烦了：

为了解决模意义下的除法问题，我们引入了逆元。$inv(a)$其实可以看作是模$p$意义下的$\frac{1}{a}$，那么在模$p$意义下，$\frac{a}{b}$就可以变成$a*inv(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$，则有$a^{p-1}\equiv1(mod\ p)$

从逆元的定义可以推导：$a*inv(a)\equiv a^{p-1}(mod\ p)$，于是有$inv(a)\equiv a^{p-2}(mod\ p)$。

于是对$a^{p-2}$算一下快速幂即可。注意：这个方法的前提是：$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 【模板】乘法逆元）

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

因为这道题要求一系列的乘法逆元，而且数据范围是$1n*10^{6} $ ，常规方法是行不通的。这里介绍逆元的线性递推求法（需保证$p$是质数）。

设$p=aq+r$，即$q=\lfloor p/a \rfloor，r=p\ mod\ a$。

在模$p$意义下，有$aq+r\equiv 0\ (mod\ p)$。

整理可得：$a=-r*inv(q)\ (mod\ p)$。

那么$inv(a)=-q*inv(r)\ (mod\ p)$。

即：$inv(a)=-\lfloor p/a \rfloor *inv(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;
}