求逆元的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 <ｐ)$
则　$ａ　＝　k × p × b + x × b$
$a mod p × b = x × b$
$x = a mod (p × b) / b$

附两道练习题：