class="markdown_views prism-dracula"> 乘法逆元的定义貌似是基于群给出的，比较简单地理解，可以说是倒数的概念的推广。记a的关于模p的逆元为$a^{-1}$,则$a^{-1}满足aa^{-1}≡ 1 (mod p)$ 加减乘与模运算的顺序交换不会影响结果，但是除法不行。有的题目要求结果mod一个大质数，如果原本的结果中有除法，比如除以a,那就可以乘以a的逆元替代。 在mod p的运算中，a存在乘法逆元当且仅当a与p互质。一般题目给的是一个大质数，所以只要a不是p的倍数，就以求乘法逆元。 目前了解到的求法有三种：
1.扩展欧几里得。$aa^{-1}≡ 1(mod p)$，可以转换为$aa^{-1} + py = 1$，即是扩展欧几里得所能解的ax + by = gcd(a, b)。最常用的解法。(p可以不是质数,但a、p必须互质) int x, y; int extgcd(int a, int b, int &x, int &y) { if (b == 0){ x = 1; y = 0; return a; } int gcd = exgcd(b, a % b, x, y); int tmp = x; x = y; y = tmp - (a/b) * y; return gcd; } /* 求解ax+by=gcd(a,b)，亦即ax≡1(mod b)。函数返回值是a,b的最大公约数，而x即a的逆元。 注意a, b不能写反了。 */ 2.由费马小定理$a^p-1≡ 1(mod p)(p为素数)$，稍作变形即是 $aa^{p-2}≡ 1(mod p)$，是不是发现了，$a^{p-2}$即是a的逆元，这个可以用快速幂来求。(p必须为质数) 当模p不是素数的时候需要用到欧拉定理
$a^{phi(p)}≡1 (mod p)$
$a*a^{phi(p)-1}≡1 (mod p)$
$a^{-1}≡a^{phi(p)-1} (mod p)$
所以$a^{phi(m)−1}$为a的逆元
时间复杂度$O(sqrt n)$即求出单个欧拉函数的值
(当p为素数的时候$phi(p)=p-1$,则$phi(p)-1=p-2$可以看出欧拉定理是费马小定理的推广)
PS：很少会用欧拉定理求逆元 3.逆元打表
有时会遇到这样一种问题，在模质数P下，求1~n逆元 n< P（这里为奇质数）。可以O(n)求出所有逆元，有一个递推式如下
$inv[i]=(P-P/i)*inv[P\%i]\%P$
它的推导过程如下，设$t=P/i,k=P\%i$,那么
$Rightarrow t*i+kequiv 0pmod P\ Rightarrow -t*iequiv k pmod P$
对上式两边同时除，进一步得到
$-t*inv[k] equiv inv[i] pmod P$
再把和替换掉，最终得到
$inv[i]=(P-P/i)*inv[P\%i]\%P$
初始化inv[1]=1，这样就可以通过递推法求出1->n模奇素数M的所有逆元了。
另外有个结论1P模P的所有逆元值对应1P中所有的数，比如P=7，那么1~P对应的逆元是$1,4 ,5 ,2 ,3 ,6$ typedef long long ll; const int N = 1e5 + 5; int inv[N]; void inverse(int n, int p) { inv[1] = 1; for (int i=2; i<=n; ++i) { inv[i] = (ll) (p - p / i) * inv[p%i] % p; } }