数论补锅之乘法逆元

69 阅读 0 评论 46 点赞

我是靠谱客的博主土豪马里奥，最近开发中收集的这篇文章主要介绍数论补锅之乘法逆元，觉得挺不错的，现在分享给大家，希望可以做个参考。

在做题的过程中，我们经常会遇到 $small frac{1}{x}$ $small %$ % $small mod$ 求算结果的情况

这个等价于求算 $small x$ 的乘法逆元

1.mod（模数）为质数时

利用费马小定理有： $small a$ 在模 $small mod$ 的意义下的乘法逆元 = $small a^{mod-2}$

代码实现为快速幂，求解一个 $small a$ 的时间复杂度为 $large log_{2}^{a}$

2.利用扩展欧几里德算法求解

将原式转化为 $large a*x+mod *y=1$

求出 $large x$ ，最后求出最小正整数解：( x % mod + mod ) % mod

3.O（n）线性求解

用于求解连续数字的逆元例如：洛谷乘法逆元模版

代码如下：


inv[1]=1;
for (int i=2;i<=n;++i)
inv[i]=(-(mod/i)*(LL)inv[mod%i]%mod+mod)%mod;

4.O（n）求阶乘的逆元

持续更新。。。

以上就是土豪马里奥为你收集整理的数论补锅之乘法逆元的全部内容，希望文章能够帮你解决数论补锅之乘法逆元所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

数论补锅之 乘法逆元