本文章为乘法逆元详解。

前一到二节属于前置知识：同余。

乘法逆元的讲解从第三节开始。

一、同余运算

\((a+b)\bmod m=[(a\bmod m)+(b\bmod m)]\bmod m\)

\((a-b)\bmod m=[(a\bmod m)-(b\bmod m) + m]\bmod m\)

\((a\times b) \bmod m = [(a \bmod m) \times (b \bmod m)] \bmod m\)

\((a\div b) \bmod m ≠ [(a \bmod m) \div (b \bmod m)] \bmod m\)

如：\((12\div3) \bmod 6 = 4 ≠ (12 \bmod 6) \div (3 \bmod 6)\)

二、同余性质

若 \(a \equiv b\pmod m\)，则 \(m|(a-b)\)。

同加性，若 \(a\equiv b\pmod m\)，则 \(a+c \equiv b+c \pmod m\) 。

同乘性，若 \(a \equiv b \pmod m\)，则 \(ac \equiv bc \pmod m\) 。

逆性质：若 \(ac \equiv bc \pmod m\) ，且 \(\gcd(c,m)=1\)，有 \(a \equiv b \pmod m\)。

证明：\(ac-pm=bc-qm\) ，\((a-b)c=(p-q)m\)，\(c\) 与 \(m\) 互质，证明 \(a-b\) 为 \(m\) 的倍数，则 \(a \equiv b \pmod m\)。

同幂性：若 \(a\equiv b\pmod m\)，则 \(a^c\equiv b^c\pmod m\)。

三、乘法逆元

对于任意整数 \(a\) 而言，如果 \(a\) 和 \(p\) 互质，存在一个整数 \(x\) 使得 \(a\times x \equiv 1\pmod p\) ，则有：

\[\begin{aligned} b\div a\bmod p&=b\div a\times(a\times x)\bmod p \\&=b\div (a\times a)\times x\bmod p\\&=b\times x\bmod p \end{aligned}

\]

\(x\) 为 \(a\) 在模 \(p\) 意义下的乘法逆元，写作 \(a^{-1}\)。

我们可以借此解决运算法则四遇到的问题。

例如： \(2\times 5 \equiv 1\pmod 9\)，则 \(5\) 是 \(2\) 关于模 \(9\) 的乘法逆元。所以 \(8\div2\bmod9=8\times5\bmod9=4\)。

有了乘法逆元之后，\(b\div a\bmod p\)，如果 \(a，p\) 互质，那么就有：

\[b\div a\bmod p=(b\bmod p\times a^{-1}\bmod p)\bmod p

\]

四、如何求乘法逆元

1.费马小定理

费马小定理：若 \(p\) 是质数，对任意整数 \(a\) 不是 \(p\) 的倍数，有 \(a^{p-1}\equiv 1\pmod p\)，也可以写作 \(a^{p}\equiv a\pmod p\)。

证明：根据同余的性质，\(a,2a,3a……,(p-1)a\) 分别 \(\bmod p\) 的结果各不相同。那么：

\[\begin{aligned}a\times2a\times3a……\times(p-1)a&\equiv 1\times2\times 3……\times(p-1)\pmod p\\a^{p-1}\times[1\times2\times 3……\times(p-1)]&\equiv1\times2\times 3……\times(p-1)\pmod p\\a^{p-1}&\equiv 1\pmod p\end{aligned}

\]

如何求乘法逆元： 若 \(p\) 是质数，则有 \(a^{p-1}\equiv 1\pmod p\)，而 \(a\times x\equiv 1\pmod p\)，所以 \(a^{p-2}\) 是 \(a\) 模 \(p\) 意义下的的乘法逆元。

可以用快速幂，时间复杂度为 \(O(\log p)\)。

2.快速求阶乘逆元

\[\begin{aligned} a\over{(n-1)!}&{\equiv} {{a}\over{n!}}\times n{\pmod p}\\ [(n-1)!]^{-1}&\equiv (n!)^{-1}\times n\pmod p\end{aligned}

\]

\(inv[n]\) 表示 \(n\) 的阶乘在模 \(p\) 意义下的的乘法逆元 \((n

可以先用费马小定理先求出 \(inv[n]\)，接着推出所有逆元。

3.快速求连续自然数逆元

假设已知 \(i=1\) 的逆是 \(1\)。递推求 \(i>1\) 时的逆。

设\(k\) 是 \(p\div i\) 的商，\(r\) 是 \(p\div i\) 的余数，则 \(k\times i+r\equiv 0\pmod p\)；

在等式两边同乘 \(i^{-1}\times r^{-1}\)，得到 \(k\times r^{-1}+i^{-1}\equiv 0\pmod p\)；

移项得到 \(i^{-1}\equiv -k\times r^{-1}\pmod p\)，即 \(i^{-1}\equiv -\lfloor{{p}\over{i}} \rfloor\times r^{-1}\pmod p\)；

最后右边加上 \(p\) ，得到 \(i^{-1}\equiv p-\lfloor{{p}\over{i}} \rfloor\times r^{-1}\pmod p\)。

下面是洛谷 P3811 乘法逆元 的部分代码：

long long inv[maxn];

void inverse(long long n, long long p){

inv[1] = 1;

for(int i = 2; i <= n; ++i)

inv[i] = (p - p/i) * inv[p % i] % p;

}

4.非连续数字快速求逆元

设有 \(n\) 个非连续数字，快速求逆元。

仍然使用快速幂，复杂度为 \(O(n\log n)\)，并非最优。

设：

非连续数字为 \(a_1，a_2，a_3……a_n\)；

\(s[i]=a_1\times a_2\times ……\times a_i\)；

\(e[i]=a_n\times a_{n-1}\times……\times a_i\)；

\(INV=(a_1\times a_2\times ……\times a_n)\)的逆元。

则 \(inv[i]=INV\times s[i-1]\times e[i+1]\)。

这样可以 \(O(n)\) 得到所有数的逆元。

下面给出洛谷 P5431 乘法逆元 2 的代码

#include

#define REG register

using namespace std;

const int maxn = 5000006;

inline int Read(); void Rite(int x);

int n;

int p,k,a[maxn],s[maxn],e[maxn],inv[maxn];

int INV = 1,ans = 0;

int power(int a,int b){

int ans = 1 % p;

for(;b;b >>= 1){

if(b & 1) ans = 1ll * ans * a % p;

a = 1ll * a * a % p;

}

return ans;

}

int main(){

n = Read(); p = Read(); k = Read();

s[0] = 1; e[n + 1] = 1;

for(REG int i = 1;i <= n;++i)

a[i] = Read() % p;

for(REG int i = 1;i <= n;++i)

s[i] = 1ll * a[i] * s[i - 1] % p;

for(REG int i = n;i >= 1;--i)

e[i] = 1ll * a[i] * e[i + 1] % p;

for(REG int i = 1;i <= n;++i)

INV = 1ll * INV * a[i] % p;

INV = power(INV,p - 2);

for(int i = 1;i <= n;++i)

inv[i] = 1ll * INV * s[i - 1] % p * e[i + 1] % p;

for(REG int i = 1,j = k;i <= n;++i,j = 1ll* j * k % p)

ans = (1ll * ans + 1ll * j * inv[i] % p) % p;

Rite(ans);

return 0;

}

inline int Read(){

char c = getchar();

int x = 0,f = 1;

while(c < '0' || c > '9'){

if(c == '-') f = -1;

c = getchar();

}

while(c >= '0' && c <= '9'){

x = x * 10 + c - '0';

c = getchar();

}

return x * f;

}void Rite(int x){

if(x < 0) putchar('-'),x = -x;

if(x > 9) Rite(x / 10);

putchar(x % 10 + '0');

}

五.结束