数论补锅之乘法逆元

81 阅读 0 评论 54 点赞

我是靠谱客的博主土豪马里奥，这篇文章主要介绍数论补锅之乘法逆元，现在分享给大家，希望可以做个参考。

在做题的过程中，我们经常会遇到 $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）求阶乘的逆元

持续更新。。。

以上就是土豪马里奥最近收集整理的关于数论补锅之乘法逆元的全部内容，更多相关数论补锅之内容请搜索靠谱客的其他文章。

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

数论补锅之 乘法逆元