逆元的求法（欧拉定理、阶乘逆元、费马小定理、模质数p的情况）

• 乘法逆元

乘法逆元

对于缩系中的元素，每个数a均有唯一的与之对应的乘法逆元x，使得 $_math_inline$ax\equiv 1\left(\text{mod}n\right)$math_inline_$ ，一个数有逆元的充分必要条件是gcd(a,n)=1，此时逆元唯一存在

在一般数学中，我们所说的逆元就是倒数，但是在数论中，如果一个数字a存在一个对p的逆元x，就可以写成 $_math_inline$ax\equiv 1\left(\text{mod}p\right)$math_inline_$ 的形式(此处p与a互质，若不互质，则不存在逆元)

逆元的含义：模n意义下，1个数a如果有逆元x，那么除以a相当于乘以x。

满足 $_math_inline$a \times k\equiv 1(\text{mod}p)的k值就是a关于p的乘法逆元$math_inline_$

当我们要求 $_math_inline$\frac{a}{b}\text{mod}p$math_inline_$ 的值时，我们就可以用到乘法逆元。我们可以用过求b关于p的乘法逆元k，将a乘上k再模p，即 $_math_inline$(a \times k)\text{mod}p$math_inline_$ 。其结果与 $_math_inline$\frac{a}{b}\text{mod}p$math_inline_$ 等价

拓展欧几里得

**拓展欧几里得:** $_math_inline$ax+by=\gcd(a,b)$math_inline_$ 的解一定存在

当我们要求 $_math_inline$a$math_inline_$ 关于 $_math_inline$p$math_inline_$ 的逆元时，若逆元存在，则 $_math_inline$\gcd(a,p)=1$math_inline_$ 。假设逆元为 $_math_inline$x$math_inline_$ ，即： $_math_inline$ax \equiv 1(\text{mod}p)$math_inline_$

我们可以展开一下变成 $_math_inline$ax=1+pk$math_inline_$ ，由于 $_math_inline$k$math_inline_$ 可正可负，我们可以得到 $_math_inline$ax+pk=1$math_inline_$ ，其实就是 $_math_inline$ax+by=\gcd(a,b)$math_inline_$ 。

我们用拓展欧几里得求出一个最小的x就是 $_math_inline$a$math_inline_$ 关于 $_math_inline$p$math_inline_$ 的一个逆元。

求解：

现在我们已经有了 $_math_inline$ax+by=\gcd(a,b)$math_inline_$ 了。我们想试着求出一个特解 $_math_inline$x$math_inline_$ 。

根据欧几里得算法我们可以知道 $_math_inline$\gcd(a,b)=\gcd(b,a\%b)$math_inline_$ 。

而且我们可以看出 $_math_inline$bx+(a\%b)y = \gcd(b,\%b)$math_inline_$

由此我们可得：(由于两边 $_math_inline$x$math_inline_$ , $_math_inline$y$math_inline_$ 值不用，我们用 $_math_inline$x'$math_inline_$ 和 $_math_inline$y'$math_inline_$ 进行区分)

我们想要把式子简化一下，可以从 $_math_inline$a\%b$math_inline_$ 入手，即 $_math_inline$a\%b=a-\lfloor \frac{a}{b} \rfloor\times b$math_inline_$ 。

所以我们可以化简得到 $_math_inline$ax+by=bx'+(a-\lfloor \frac{a}{b} \rfloor\times b)y'$math_inline_$

移项： $_math_inline$ax+by=ay'+b(x'-\lfloor \frac{a}{b} \rfloor y')$math_inline_$

系数相等，所以我们可以解得

根据欧几里得算法，我们一直递归下去，总会到 $_math_inline$a\%b=0$math_inline_$

所以式子变成了 $_math_inline$ax=\gcd(a,b)$math_inline_$ 。此时我们取一个特解 $_math_inline$x=1,y=0$math_inline_$ 。然后往回推，就可以得到一开始的那个x。

此时解出来的 $_math_inline$x$math_inline_$ 就是 $_math_inline$a$math_inline_$ 关于 $_math_inline$p$math_inline_$ 的一个逆元。

PS：算法效率较高，常数较小，时间复杂度 $_math_inline$O(\ln{n})$math_inline_$

 1void exgcd(LL a, LL b, LL &x, LL &y) {
 2	if (b == 0) {
 3		x = 1;y = 0;
 4	} else {
 5		exgcd(b, a%b, y, x);
 6		y -= (a/b) * x;
 7	}
 8}
 9
10void extgcd(LL a, LL b, LL &d, LL &x, LL &y) {
11    if (!b) {
12        d = a;        
13        x = 1;
14        y = 0;
15    } else {
16        extgcd(b, a % b, d, y, x);
17        y -= x * (a / b);
18    }
19}
20
21LL inverse(LL a, LL n) {
22    LL d, x, y;
23    extgcd(a, n, d, x, y);
24    return d == 1 ? (x + n) % n : -1;
25}

递推求阶乘逆元

我们经常会用到阶乘的逆元，我们可以考虑用费马小定理先求出最大的那个阶乘的逆元，然后再往回推

我们可以把 $_math_inline$n!$math_inline_$ 的逆元表示为 $_math_inline$\left[n!\right]^{-1}$math_inline_$ 。

我们要求 $_math_inline$(n-1)!$math_inline_$ 的逆元，我们可以考虑给 $_math_inline$(n-1)!$math_inline_$ 乘上一个 $_math_inline$n$math_inline_$ 把他变为 $_math_inline$n!$math_inline_$ 。

即 $_math_inline$(n-1)!\times n\left[n!\right]^{-1} \equiv 1\text{mod}p$math_inline_$

因此 $_math_inline$\left[n!\right]^{-1}$math_inline_$ 是 $_math_inline$(n-1)!$math_inline_$ 关于 $_math_inline$p$math_inline_$ 的一个逆元。

 1void init() {
 2	fact[0] = 1;
 3	for (int i = 1; i < maxn; i++) {
 4		fact[i] = fact[i - 1] * i %mod;
 5	}
 6	inv[maxn - 1] = power(fact[maxn - 1], mod - 2);
 7	for (int i = maxn - 2; i >= 0; i--) {
 8		inv[i] = inv[i + 1] * (i + 1) %mod;
 9	}
10}

费马小定理

在模为素数p的情况下，有费马小定理 $_math_inline$a^{p-1}\equiv 1(\text{mod}p)$math_inline_$ ，（左右同除a）得 $_math_inline$a^{p-2}=a^{-1}(\text{mod}p)$math_inline_$ ，也就是说a的逆元为 $_math_inline$a^{p-2}$math_inline_$

而在模数不为素数p得情况下，有欧拉定理 $_math_inline$a^{phi(m)}\equiv q (\text{mod}m)\quad(a \perp m)$math_inline_$

同理 $_math_inline$a^{-1}=a^{phi(m)-1}$math_inline_$

因此逆元x便可以套用快速幂求得了 $_math_inline$x=a^{phi(m)-1}$math_inline_$

如何判断a是否有逆元？检验逆元的性质，看求出的幂值x与a相乘是否为1即可

PS：这种算法复杂度为 $_math_inline$O(\log_2(N))$math_inline_$ 在几次测试中，常数似乎较上种方法大

当p比较大的时候需要用快速幂求解

1LL pow_mod(LL x, LL n, LL mod) {
2    LL res = 1;
3    while (n > 0) {
4        if (n & 1)res = res * x % mod;
5        x = x * x % mod;
6        n >>= 1;
7    }
8    return res;
9}

当模p不是素数的时候需要用到欧拉定理

所以时间复杂度即求出单个欧拉函数的值

(当p为素数的时候 $_math_inline$phi(p)=p-1$math_inline_$ ，则 $_math_inline$phi(p)-1=p-2$math_inline_$ 可以看出欧拉定理是费马小定理的推广)

PS：这里就贴出欧拉定理的板子，很少会用欧拉定理求逆元

特殊情况

一

当N是质数，这点也很好理解。当N是质数， $_math_inline$0

CF 696C

二

求逆元一般公式(条件b|a)

证明：

PS：实际上 $_math_inline$\frac{a\text{mod}(bm)}{b}$math_inline_$ 这种对于所有的都适用，不区分互补互素，而费马小定理和拓展欧几里得算法求逆元是有局限性的，它们都会要求a与m互素，如果a与m不互素，那就没有逆元，这个时候需要 $_math_inline$\frac{a\text{mod}(bm)}{b}$math_inline_$ 来搞（此时就不是逆元的概念了）。但是当a与m互素的时候，bm可能会很大，不适合套这个一般公式，所以大部分时候还是用逆元来搞

通过递推求1~n的逆元

有时候会遇到这样一种问题，在模质数p下，求 $_math_inline$q\sim n$math_inline_$ 逆元 $_math_inline$n $_math_inline$inv[i]=(M-\frac{M}{i}) \times inv[M\%i]\%M$math_inline_$

推导过程如下，设 $_math_inline$t=\frac{M}{i} \quad k=M\%i$math_inline_$

左右同时除 $_math_inline$i \times k$math_inline_$ ，得到

再把t和k替换掉

初始化 $_math_inline$inv[1]=1$math_inline_$ ，这样就可以通过递推法求出1->n模奇素数p的所有逆元了

另外有个结论 1->p 模 p的所有逆元值对应 1->p 中所有的数，比如p=7，那么 1->6 对应的逆元是 1 4 5 2 3 6

1const int N = 1e5 + 5;
2int inv[N];
3
4void inverse(int n, int p) {
5    inv[1] = 1;
6    for (int i = 2; i <= n; ++i) {
7        inv[i] = (ll) (p - p / i) * inv[p % i] % p;
8    }
9}

通过递推求n!的逆元

递推公式： $_math_inline$invf[i]=invf[i+1]\times(i+1)\%p$math_inline_$

 1// 快速幂求逆元
 2int quick_inverse(int n, int p) {
 3	int ret = 1;
 4	int exponent = p - 2;
 5	for (int i = exponent; i; i >>= 1, n = n * n % p) {
 6		if (i & 1) {
 7			ret = ret * n % p;
 8		}
 9	} 
10	return ret;
11}
12int invf[N], factor[N];
13void get_factorial_inverse(int n, int p) {
14	factor[0] = 1;
15	for (int i = 1; i <= n; ++i) {
16		factor[i] = i * factor[i - 1] % p;
17	}
18	invf[n] = quick_inverse(factor[n], p);
19	for (int i = n-1; i >= 0; --i) {
20		invf[i] = invf[i + 1] * (i + 1) % p;
21	}
22}

题目

POJ-1845