# 逆元

# 什么是逆元?

ax1(modb)ax \equiv 1 \pmod b,则称 xxaa 关于模 bb 的逆元,常记做 a1a^{-1}

上式等价于 ax+by=1ax + by = 1,因此,一种求逆元的方法就是利用扩欧解方程 ax+by=1ax + by = 1

显然,逆元不一定存在:其存在的充要条件为 (a,b)=1(a, b) = 1

推论:pp 是质数,pp 不整除 aa,则 aapp 的逆元存在。

结论:在 [0,b)[0, b) 的范围内,aa 关于模 bb 的逆元(若存在)是唯一的。

证明:
反证法,若 aa 有两个逆元 0<x1<x2<b0 < x_1 < x_2 < b
ax1ax21(modb)ax_1 ≡ ax_2 ≡ 1 \pmod b
那么有 ba(x2x1)b|a(x_2 - x_1) 成立。
又由于 (a,b)=1(a, b) = 1,因此 b(x2x1)b|(x_2 - x_1)
其中 0<x2x1<b0 < x_2 - x_1 < b,产生了矛盾。

# 求解逆元

ax1(modp)ax\equiv 1 \pmod p

# 扩欧

上面已经提到过了,直接解方程 ax+py=1ax + py = 1 即可。这个方法十分容易理解,而且对于单个查找效率不错,尤其是在模数比较大的时候。

这个做法在 a,pa,p 互质,但 pp 不是质数时也可以使用。其他方法均要求 pp 必须为素数。

# 快速幂

这个做法要利用费马小定理:若 pp 为素数,aa 为正整数,且 a,pa,p 互质,则有

ap11(modp)a^{p-1} \equiv 1 \pmod {p}

因此,

ax1(modp)axap1(modp)xap2(modp)\begin{aligned} ax&\equiv 1 &\pmod p\\ \Rightarrow ax&\equiv a^{p-1} &\pmod p\\ \Rightarrow x &\equiv a^{p-2} &\pmod p \end{aligned}

用快速幂算出 ap2(modp)a^{p-2} \pmod p 的值,这个数就是它的逆元了。

# 递推

用于求连续的数对于同一模数的逆元。

# P3811 【模板】乘法逆元

首先有 111(modp)1^{-1}\equiv 1 \pmod p

然后设 p=ki+r(1<r<i<p)p=ki+r(1<r<i<p),即 kkpi\frac{p}{i} 的商,rr 是余数。

再将这个式子放到模 pp 意义下,有

k×i+r0(modp)k\times i+r \equiv 0 \pmod p

两边乘上 i1r1i^{-1}r^{-1},有

k×r1+i10(modp)i1k×r1(modp)i1pi(pmodi)1(modp)\begin{aligned} k\times r^{-1}+i^{-1}&\equiv 0 &\pmod p\\ \Rightarrow{}i^{-1}&\equiv -k\times r^{-1} &\pmod p\\ \Rightarrow{}i^{-1}&\equiv -\lfloor \frac{p}{i} \rfloor*(p \bmod i)^{-1} &\pmod p \end{aligned}

于是,我们就可以递推求得逆元了。

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
long long inv[int(3e6+10)]; int n, p;
int main() {
	
	scanf("%d%d", &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) printf("%lld\n", inv[i]);
	return 0;
}

# 阶乘

首先有这样一个结论:1n!=1n×1(n1)!\frac{1}{n!}=\frac{1}{n}\times\frac{1}{(n-1)!},即 (n1)!(n-1)! 的逆元等于 n!n! 的逆元乘 nn

因此,我们求出 n!n! 的逆元然后逆推,可以求出 1!,2!,,n!1!,2!,\dots,n! 的逆元;又 1n!×(n1)!=1n\frac{1}{n!}\times(n-1)!=\frac{1}{n}n!n! 的逆元乘上 (n1)!(n-1)! 可以得到 nn 的逆元。

更新于