乘法逆元:扩展gcd与欧拉phi函数

jys posted @ Mar 16, 2013 12:47:02 AM in 未分类 , 3082 阅读

在计算一个很大的组合数modP时会用到乘法逆元。即把/a变成*(f(a)),其中f(a)为a在模P意义下的乘法逆元,即a*f(a) mod P=1

计算乘法逆元有两种方法,扩展gcd或基于欧拉公式的快速幂取模。

------------------------------------------------------------------------------------------------------

扩展gcd就是求解方程ax=1(mod P)的最小整数解.

设ax=1+y*p,即a*f(a,p)=1+p*g(a,p),把x和y的解看成关于a,p的函数。

a>=p时,设a=p*k+r,则式子变成:

p*k*f(a,p)+r*f(a,p)=1+p*g(a,p),移项,得r*f(a,p)=1+p*(g(a,p)-k*f(a,p))

那么就得到f(a mod p,p)=f(a,p),g(a mod p,p)=g(a,p)-[a/p]*f(a,p);

p>=a时差不多一个意思。

所以把f,g设成全局变量,像普通gcd那样做,即时更新f,g即可。

----------------------------------------------------------------------------------------------------

设欧拉函数phi(x)=在[1,x-1]中与x互质的数字个数。那么欧拉公式:

a^phi(P)=1(mod P)

两边同除a,即可得到a^(phi(P)-1) mod P即为a在模P意义下的乘法逆元。

特例:

如果P是质数,那么phi(P)=P-1.即a的乘法逆元为a^(P-2),快速幂即可。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter