求逆元的N种方法

昨天打了一场bestcoder,赛后阅读大神们的AC代码发现了好多种求逆元的方法,于是就在此总结一下。

方法1.通过扩展欧几里得算法求逆元

这是我接触到的第一个求逆元的算法,高中时也只会这一种求逆元的方法。NOIP2012 day2的第一题就是一道裸的求逆元的问题,当时仅用了5分钟就敲完了,感觉还挺爽的。不过这种方法现在基本不用了……原理很简单,就不分析了,直接上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// when we used this method to calculate x / y % p, we also need x and p is coprime
// Method 1: Extended Euclid
// Requires: a and b is coprime
// Modify: x, y
// Effects: when the method is finished, x is a's inverse element about b.
// Return: gcd(a, b)
int ex_gcd(int a, int b, int &x, int &y) {
int ret, tmp;
if (b == 0) {
x = 1;
y = 0;
return a;
}
ret = ex_gcd(b, a % b, x, y);
tmp = x;
x = y;
y = tmp - a / b * y;
return ret;
}

方法2.通过快速幂求逆元

这个方法要求模的数必须为质数。根据费马小定理,有$n^{p-1} \equiv 1 (mod p)$。因此$\frac{1}{n} \equiv n^{p-2} (mod p)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// when we used this method to calculate x / y % p, we also need x and p is coprime
// Method 2: Quick Power
// Requires: p is prime
// Modify: none
// Effects: return n's inverse element about p
// Return: n's inverse element about p
int quick_inverse(int n, int p) {
int ret = 1;
int exponent = p - 2;
for (int i = exponent; i; i >>= 1, n = n * n % p) {
if (i & 1) {
ret = ret * n % p;
}
}
return ret;
}

方法3.通过递推求1~n的逆元

这个递推式为:

$inv[i] = (p - \frac{p}{i}) × inv[p \% i] \% p$;

推导过程如下:

设$t = \frac{p}{i}$; $k = p \% i$;
则有: $t × i + k \equiv 0 (mod p)$
进一步有: $-k \equiv t × i (mod p)$
对该式两边分别除以$i × k$,得:
$-inv[i] \equiv t × inv[k] (mod p)$
将$t$, $k$代入,即得:
$inv[i] \equiv (p - p / i) × inv[p % i] (mod p)$

这个算法可以在$O(n)$的时间复杂度内求出n以内所有数的逆元,不过需要注意的是$p$必须为奇质数。

1
2
3
4
5
6
7
8
9
10
11
12
13
// when we used this method to calculate x / y % p, we also need x and p is coprime
// Method 3: Recursive to get i's inverse element
// Requires: p is prime and p != 2
// Modify: inv[]
// Effects: inv[i] is i's inverse element about p;
int inv[N];
void get_inverse(int n, int p) {
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (p - p / i) * inv[p % i] % p;
}
}

特殊情况1.通过递推求$n!$的逆元

在某些题目中,我们会用到$n!$的逆元,这时有一种简单的递推方法,可以倒序求出$1!$ ~ $n!$的逆元。

递推公式:

$invf[i] = invf[i + 1] × (i + 1) \% p$;

这个公式非常容易证得,这里不再证明。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// when we used this method to calculate x / y % p, we also need x and p is coprime
// Method 4: Recursive to get Factorial[i] and their inverse element
// Requires: p is prime
// Modify: invf[], factor[]
// Effects: factor[i] is i's factorial, invf[i] is factor[i]'s inverse element
int invf[N], factor[N];
void get_factorial_inverse(int n, int p) {
factor[0] = 1;
for (int i = 1; i <= n; ++i) {
factor[i] = i * factor[i - 1] % p;
}
invf[n] = quick_inverse(factor[n], p);
for (int i = n-1; i >= 0; --i) {
invf[i] = invf[i + 1] * (i + 1) % p;
}
}

特殊情况2.某些时候不能简单求逆元

对于上面几种解法,都基于一个共同的前提:

如果要求的是 $a / b (mod p)$,那么$a$与$p%必须互质。

因此在某些$a$与$p$不互质的情况下,就不能用简单的$a / b \equiv a × inv[b] (mod p)$来计算了。

不过,有一个通用的解法是:

$a / b mod p = a mod (b × p) / b$
当然, 要满足 $b|a$.

证明过程如下:

设 $a / b = k × p + x (x <p)$
则 $a = k × p × b + x × b$
$a mod p × b = x × b$
$x = a mod (p × b) / b$

附两道练习题: