首页 > 代码库 > 【奇技淫巧】数学技巧之乘法逆元

【奇技淫巧】数学技巧之乘法逆元

一、写在前面

开始码这篇blog之前我就意识到,这篇blog将会是我到目前为止码出的所有blog中最水的一篇。说是讲乘法逆元,但蒟蒻博主自己都不会证明_(:з」∠)_所以只打算放一个说明书式的用法,还请诸位看官老爷轻喷。

二、关于乘法逆元

我们知道模法交配率(Magic Coitus Law)(←_←其实并没有这东西)并不适用于除法。用式子表示大概是这样的:

技术分享

但乘法逆元(Multiplicative Inverse Modulo,下式中用a‘表示)就可以完成这样一个奇妙的操作:

技术分享

然后我们就能用模法交配率啦(撒花~\(≧▽≦)/~

那乘法逆元怎么求呢?说了我也不知道啊┑( ̄Д  ̄)┍但我知道,当模数p为质数时,乘法逆元可以长这个样子:

技术分享

于是,我们就可以得到:

技术分享

以上,乘法逆元的说明书就到这里啦,例题什么的等我找到能用到乘法逆元的题再放吧。

弱弱地说一句,本蒟蒻码字也不容易,转载请注明出处http://www.cnblogs.com/Maki-Nishikino/p/6057739.html

【奇技淫巧】数学技巧之乘法逆元