目录
- 什么是逆元
- 如何求逆元
- 阶乘逆元
- 线性求逆元
本文章内，若无特殊说明，数字指的是整数，除法指的是整除。
什么是逆元
我们称\(a\)是\(b\)在模\(p\)情况下的逆元，则有\(a \times b \equiv 1 ( mod\,\,p)\)。
所以呢，我们其实可以将逆元看成一个数的相反数。所以在除以一个数的时候，就相当于乘上它的相反数。
如何求逆元
我们先来看看什么情况下有逆元。
当且仅当\(gcd(b,p)=1\)时，\(b\)在模\(p\)情况下有逆元。
这个结论可由裴蜀定理显然推得，下面一段来自百度百科，若读者对证明有兴趣，可以自行了解。
裴蜀定理（或贝祖定理，Bézout's identity）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数\(a\)、\(b\)和它们的最大公约数\(d\)，关于未知数\(x\)和\(y\)的线性不定方程（称为裴蜀等式）：若\(a\),\(b\)是整数,且\((a,b)=d\)，那么对于任意的整数\(x\),\(y\),\(ax+by\)都一定是\(d\)的倍数，特别地，一定存在整数\(x\),\(y\)，使\(ax+by=d\)成立。
拓展欧几里得求逆元
下面介绍如何用拓展欧几里得求逆元。
我们求\(b\)在模\(g\)意义下的逆元，根据\(a \times b \equiv 1 ( mod\,\,p)\)，得到\(a\times b + k\times p = 1\)。
我们知道，\(gcd(b,p)=gcd(p,b \% p)\)，所以\(a'\times p+k'\times (b \% p)=1\)同样有解。而由于\(gcd(b,p)=1\)，辗转相除法时，总有\(a''\times 1 + k'' \times 0 = 1\)。
此时我们不妨令\(a''=1,k''=0\)。
现在我们考虑怎么推回去。
\[ a'\times p+k'\times (b \% p)=1 \]
\[ \Rightarrow a'\times p+k'\times( b-\left \lfloor \frac{b}{p} \right \rfloor \times p)=1 \]
\[ \Rightarrow k'\times b+(a'-\left \lfloor \frac{b}{p} \right \rfloor \times k') \times p=1 \]
与\(a\times b + k\times p = 1\)对照，得到\(a=k',\,\,\,k=a'- \left \lfloor \frac{b}{p} \right \rfloor\times k'\)。那么这样，我们就得到了\(a\times b + k\times p = 1\)的一组解，同时，\(a\)就是\(b\)在模\(p\)下的逆元。
附C++程序
#include <bits/stdc++.h>
using namespace std;
void ExPower( int b, int p, int & a, int & k ) {if( p == 0 ) {a = 1; k = 0;return;}ExPower( p, b % p, k, a );k -= b / p * a;return;
}
int main() {int b, p;cin >> b >> p;int a, k;ExPower( b, p, a, k );if( a < 0 ) a += p;cout << a << endl;return 0;
}费马小定理求逆元
我们知道，当\(p\)为素数，并且\(gcd(a,p)=1\)时，我们有\(a^{p-1} \equiv 1 (mod\,\,p)\)。那么我们就有\(a^{p-2}\times a \equiv 1(mod \,\, p)\)。所以逆元就是\(a^{p-2}\)了。
阶乘逆元
如果我们需要求\(0!\)到\(n!\)的逆元，对于每个元素都求一遍，就显得有点慢。（虽然\(exPower\)的时间快到可以认为是小常数。）
前面我们说了，逆元就可一看做是求倒数。那么不就有\(\frac{1}{(n+1)!}\times (n+1)=\frac{1}{n!}\)。
附C++程序：
int inv( int b, int p ) {int a, k;exPower( b, p, a, k );if( a < 0 ) a += p;return a;
}
void init( int n ) {Fact[ 0 ] = 1;for( int i = 1; i <= n; ++i ) Fact[ i ] = Fact[ i - 1 ] * i % Mod;INV[ n ] = inv( Fact[ n ], Mod );for( int i = n - 1; i >= 0; --i ) INV[ i ] = INV[ i + 1 ] * ( i + 1 ) % Mod;return;
}线性求逆元
按照上面的方法，如果我们要求\(1\)到\(p-1\)关于\(p\)的逆元，而\(p\)较大时，时间复杂度有点吃不消。而我们有一种更强的做法，可以在\(O(p)\)的时间内解决。
对于当前的\(i\)，我们设\(p=k\times i+r\)。于是：
\[ \begin{aligned} k \times i + r & \equiv 0 &\,\,(mod \,\, p) \\ k \times i \times ( i^{-1} \times r ^{-1}) + r \times (i^{-1} \times r^{-1}) &\equiv 0 &\,\,( mod \,\, p) \\ k \times r^{-1} + i ^ {-1} & \equiv 0 &\,\, (mod \,\, p)\\ i^{-1} & \equiv -k \times r^{-1} &\,\, (mod \,\, p) \\ i^{-1} & \equiv - \left \lfloor \frac{p}{i}\right \rfloor \times r^{-1} &\,\,(mod\,\,p) \end{aligned} \]
所以代码就大致如下：
Inv[ 1 ] = 1;
for( int i = 2; i <= n; i++ )Inv[ i ] = ( p - p / i ) * Inv[ p % i ] % p;
