求逆元基本方法

1、求逆元基本方法乘法逆元小结乘法逆元，一般用于求$fracabpmodp$的值($p$通常为质数)，是解决模意义下分数数值的必要手段。一、逆元定义若$a*xequiv1pmodb$,且$a$与$b$互质，那么我们就能定义:$x$为$a$的逆元，记为$aA-1$,所以我们也可以称$x$为$a$在$modb$B义下的倒数，所以对于$displaystylefracabpmodp$,我们就可以求出$b$在$bmodp$下的逆元，然后乘上$a$，再$bmodp$,就是这个分数的值了。二、求解逆元的方式1拓展欧几里得条件$abotp$(互质)，但$p$不是质数的时候也可以使用。这个方法十分容易理解，而且对

2、于单个查找效率似乎也还不错，比后面要介绍的大部分方法都要快尤其对于$bmodp$比较大的时候)。这个就是利用拓欧求解线性同余方程$a*xequivcpmodb$的$c=1$的情况。我们就可以转化为解$a*x+b*y=1$这个方程。引理：$ax+by=c$有解的充分条件$gcd(a,b)midc$所以$ax+by=gcd(a,b)鸟显然有解引理：$gcd(a,b)=gcd(b,amodb)$将$代入$得$ax_1+by_1=bx_2+(amodb)y_2$ax_1+by_1=bx_2+(a-fracab*b)y_2$ax_1+by_1=bx_2+ay-fracab*by_2$ax_1+by_1=

3、ay_2+b(x_2-fracab)$.x_1=y_2,y_1=x_2-fracaby$vabotb$.，.gcd(a,b)=1$当b=0时，a=1，此时有x=1,y的最小自然数解为0$代码比较简单：voidExgcd(lla,llb,ll&x,ll&y)if(!b)x=1,y=0;elseExgcd(b,a%b,y,x),y-=a/b*x;intmain()llx,y;Exgcd(a,p,x,y);x=(x%p+p)%p;printf(%dn,x);/x是a在modp下的逆元2小费尔马定理(快速幕)费马小定理：若$p$为素数，$a$为正整数，且$a$、$p$互质。则有$aAp-1equiv1

4、(bmodp)$。这个我们就可以发现它这个式子右边刚好为$1$。所以我们就可以放入原式，就可以得到：$a*xequiv1pmodp$a*xequivaAp-1pmodp$xequivaAp-2pmodp$所以我们可以用快速幕来算出$aAp-2pmodp$的值，这个数就是它的逆元了代码也很简单：llfpm(llx,llpower,llmod)x%=mod;llans=1;for(;power;power=1,(x*=x)%=mod)if(power&1)(ans*=x)%=mod;returnans;intmain()IIx=fpm(a,p-2,p);x为a在modp意义下的逆元线性推逆元用于求

5、一连串数字对于一($bmod卩$的逆元。只能用这种方法，别的算法都比这些要求一串要慢。首先我们有一个,$1A-1equiv1pmodp$然后设$p=k*i+r,(1rip)$也就是$k$是$p/i$的商，$r$是余数。再将这个式子放至U$pmodp$意义下就会得到：$k*i+requiv0pmodp$然后乘上$iA-1$,$rA-1$就可以得到：$k*rA-1+iA-1equiv0pmodp$iA-1equiv-k*rA-1pmodp$iA-1equiv-lfloorfracpirfloor*(pbmodi)A-1pmodp$于是，我们就可以从前面推出当前的逆元了。代码也很短：inv1=1;f

6、or(inti=2;ip;+i)invi=(p-p/i)*invp%i%p;阶乘逆元$O(n)$求因为有如下一个递推关系。$dispIaystyIeinvi+1=frac1(i+1)!$dispIaystyIeinvi+1*(i+1)=frac1i!=invi$所以我们可以求出$n!$的逆元，然后逆推，就可以求出$仁川$所有的逆元了。递推式为$invi+1*(i+1)=invi$所以我们可以求出$displaystyleforalli,i!,frac1i!$的取值了。然后这个也可以导出$displaystylefrac1ipmodp$的取值，也就是$dispIaystyIefrac1i!times(i-1)!=frac1ipmodp$如果我们需要求$0!$到$n!$的逆元，对于每个元素都求一遍，就显得有点慢。逆元可以看作是求倒数。那么不就有$displaystylefrac1(n+1)!times(n+1)=frac1n!pmodp$intinv(intb,intp)inta,k;exPower(b,p,a,k);if(a0)a+=p;returna;voidinit(intn)Fact0=1;for(inti=1