class="markdown_views prism-github-gist">

1.乘法逆元的定义及作用

定义（口胡）：
乘法逆元是取模运算中的一个东西。假设ax≡1(modp)" role="presentation">ax≡1(modp)$ax\equiv 1(modp)$ 并且GCD（a，p）=1 （a，p互质），那么x就是a的逆元。对于给定的a和p，有且仅有一个数是它的逆元。 乘法逆元的作用：
因为取模这个运算是不满足“除法分配率”的，这就导致了如果a，b或者p很大的话，(ab)modp" role="presentation">(ab)modp$(\frac{a}{b})\mathrm{mod}p$ 这个运算就会爆精度。那么我们就要用另外一种方法来计算这个式子，而乘法逆元给我们提供了一个很好的途径。
(ab)modp=(ab)∗1modp=(ab)∗(b∗x)modp=a∗xmodp（x为b的逆元时）" role="presentation">(ab)modp=(ab)∗1modp=(ab)∗(b∗x)modp=a∗xmodp（x为b的逆元时）$$(\frac{a}{b})\mathrm{mod}p=(\frac{a}{b})\ast 1\mathrm{mod}p=(\frac{a}{b})\ast (b\ast x)\mathrm{mod}p=a\ast x\mathrm{mod}p（x为b的逆元时）$$
这样我们就把除法变成满足Mod分配率的乘法了。

2.乘法逆元的求法

1.扩展欧几里德求逆元 什么是扩展欧几里德
此时a,p一定要满足互质
对于式子 ax≡1 (mod p) 我们可以将它变成一个方程：a∗x+p∗y=1" role="presentation">a∗x+p∗y=1$a\ast x+p\ast y=1$
由于我们前面定义中说明了GCD（a，p）=1" role="presentation">GCD（a，p）=1$GCD（a，p）=1$，此时由于裴蜀定理，该方程一定至少有一组解。我们可以用扩展欧几里德算法求得特殊解，再套用通解公式：y=y0−aGCD(a,b)∗t" role="presentation">y=y0−aGCD(a,b)∗t$y=y0-\frac{a}{GCD(a,b)}\ast t$求出满足mod p条件的一组解（也就是mod一下啦）
代码如下： int exgcd(int a,int b,int &x,int &y){ if (b==0) {x=1,y=0; return x;} int ret=exgcd(b,a%b,x,y); int t=x; x=y,y=t-a/b*y; return ret; } int calc(int n,int p){ int pd=exgcd(n,p,x,y); if (pd==1) return (x%p+p)%p; } 2.费马小定理求逆元
首先了解一下费马小定理：
p是素数时，对于任意整数x都有 xp≡x(modp)" role="presentation">xp≡x(modp)$x^p\equiv x(modp)$。
如果x为整数且x，p互质，则有 xp−1≡1(modp)" role="presentation">xp−1≡1(modp)$x^{p-1}\equiv 1(modp)$。
证明详见百度百科：传送门
那么就可以来推导了：xp−1≡x∗xp−2≡1(modp)" role="presentation">xp−1≡x∗xp−2≡1(modp)$x^{p-1}\equiv x\ast x^{p-2}\equiv 1(modp)$。那么根据乘法逆元的定义可以得到x的逆元就是xp−2" role="presentation">xp−2$x^{p-2}$。求xp−2" role="presentation">xp−2$x^{p-2}$只要用一下快速幂就好了。当然成立的条件是满足x，p互质。
代码如下： int qsm(int x,int y){ int ans=1,w=x; while (y) { if (y%2==1) ans=(ans*w)%p; y/=2; w=(w*w)%p; } return ans; } int calc(int n,int p){ return qsm(n,p-2); } 3.欧拉函数求逆元
欧拉定理：对于两个互质的正整数a,p(p>2)有:xφ(p)≡1(modp)" role="presentation">xφ(p)≡1(modp)$x^{\phi }(p)\equiv 1(modp)$。
变形一下就可以得到：x∗x(φ(p)−1)≡1(modp)" role="presentation">x∗x(φ(p)−1)≡1(modp)$x\ast x^{(\phi (p)-1)}\equiv 1(modp)$
那么我们就可以先求出欧拉函数值φ(p)然后快速幂就能够解决了。
这种方法成立的条件同样是要满足x，p互质。
注：
欧拉函数： φ(x)=x(1−1p(1))(1−1p(2))(1−1p(3))…..(1−1p(n))（p(i)表示x的第i个质因子）" role="presentation">φ(x)=x(1−1p(1))(1−1