求解乘法逆元有三种常用方法：
1、费马小定理/欧拉函数
2、扩展欧几里德算法
3、线性求逆元

取模公式

$(a+b)modp=(amodp+bmodp)modp$
$(a-b)modp=(amodp-bmodp+p)modp$
$(a\times b)modp=(amodp\times bmodp)modp$
$(a÷b)modp=(a\times b^{\phi (p)-1})modp=(amodp\times b^{\phi (p)-1}modp)modp$

乘法逆元

为了对除法算式进行取模，我们引入了乘法逆元的概念：

若存在正整数$a、b、p$满足$ab\equiv 1(modp)$，则称$a$为$b$的乘法逆元，或称$b$为$a$的乘法逆元

乘法逆元的存在性定理：

若$a$与$p$互质，则⼀定存在⼀个正整数解$b$，满⾜$b$ < $p$。
若$a$与$p$不互质，则⼀定不存在正整数解$b$。

费马小定理

在$p$为素数时，对于任意整数$x$都有$x^p\equiv x(modp)$，此定理为费马小定理。

如果$x$无法被$p$整除，有$$x^{p-1}\equiv 1(modp)$$

等价为$$x\ast x^{p-2}\equiv 1(modp)$$

可以得到$$x^{-1}\equiv x^{p-2}(modp)$$

结论：当$p$为素数时，有$$(a÷b)modp=(amodp\times b^{p-2}modp)modp$$

可以利用快速幂来求出逆元，复杂度为$O(logn)$

欧拉函数

$\phi (m)=$不超过$m$并且和$m$互素的数的个数

对于和$m$互素的$x$，有

$$x^{\phi (m)}\equiv 1(modm)$$

等价为$$x\ast x^{\phi (m)-1}\equiv 1(modm)$$

根据逆元的定义式，有

$$x^{-1}\equiv x^{\phi (m)-1}(modm)$$

结论：$$(a÷b)modp=(a\times b^{\phi (p)-1})modp=(amodp\times b^{\phi (p)-1}modp)modp$$

求解$\phi (n)$的时间复杂度为$O(\sqrt{n})$，求出$\phi (n)$后可以利用快速幂来求出逆元，用这种方法求逆元的时间复杂度为$O(\sqrt{n}\ast logn)$

求解欧拉函数值的代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int euler_phi(int n)
{
int res = n;
for (int i = 2; i * i <= n; i++){
if (n % i == 0){
res = res / i * (i - 1);
for ( ; n % i == 0; n /= i);
}
}
if (n != 1)
res = res / n * (n - 1);
return res;
}
int main(void)
{
int n;
cin >> n;
int ans = euler_phi(n);
cout << ans << endl;
return 0;
}

扩展欧几里得算法

常用于求$ax+by=gcd(a,b)$的一组可行解。返回值为$gcd(a,b)$，同时计算出$x$和$y$。

可以用于求解逆元，根据逆元的定义：$$ax\equiv 1(modb)$$

可以得出不定方程：$$ax+by=1$$

当$gcd(a,b)=1$时，上述方程一定有解，所以一定存在一个$x$为$a$的乘法逆元。

将$a、b$的值代入方程$ax+by=1$，就可以利用扩展欧几里得算法解出这个方程，解出的$x$即为$a$的乘法逆元。

用该算法求出的$|x|+|y|$是最小的。如果$ab\ne 0$，还可以知道$|x|\le b且|y|\le a$，但并不能保证$x$是正数，需要进行$x=(b+x\%b)\%b$这样的操作来得到最小正整数$x$

这个算法的时间复杂度为$O(logn)$

扩展欧几里得算法求逆元的代码

#include <cstdio>
#include <iostream>
using namespace std;
int exgcd(int a, int b, int& x, int& y)
{
int d = a;
if (b != 0){
d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
}
else{
x = 1;
y = 0;
}
return d;
}
int main(void)
{
int a, b, x, y;
cin >> a >> b;
cout << exgcd(a, b, x, y) << endl;
x = (b + x % b) % b;
cout << x << endl;
return 0;
}

线性求逆元

此部分内容转载自：https://www.cnblogs.com/qdscwyy/p/7795368.html

设$p=k\ast i+r，(r<i，1<i<p)$

将式子放到$modp$意义下，有
$$k\ast i+r\equiv 0(modp)$$
两边同乘$i^{-1}\ast r^{-1}$，得
$$k\ast r^{-1}+i^{-1}\equiv 0(modp)$$
移项，得
$$i^{-1}\equiv -k\ast r^{-1}(modp)$$
用已知的$p、i$表示$k、r$，得
$$i^{-1}\equiv -\lfloor \frac{p}{i}\rfloor \ast (pmodi{)}^{-1}(modp)$$

根据上面推出的公式，可以用前面的逆元推出当前的逆元

用式子表示时，负数取模的值等于加模数到正数后再取模的值，而写程序时不能直接用负数来计算，需要先加一个模数使其为正，就像下面这样

inv[i] = ((p - p / i) * inv[p % i]) % p;

此方法适用于求从1——n连续的逆元，时间复杂度为$O(n)$

线性求解逆元的代码

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 3e6 + 5;
typedef long long ll;
ll inv[N];
void pre(int p)
{
inv[1] = 1;
for (int i = 2; i <= N - 5; i++)
inv[i] = ((p - p / i) * inv[p % i]) % p;
}
int main(void)
{
int n, p;
scanf("%d%d", &n, &p);
pre(p);
for (int i = 1; i <= n; i++)
printf("%lldn", inv[i]);
return 0;
}

最后

以上就是爱撒娇黑米为你收集整理的求解乘法逆元的方法取模公式乘法逆元费马小定理欧拉函数扩展欧几里得算法线性求逆元的全部内容，希望文章能够帮你解决求解乘法逆元的方法取模公式乘法逆元费马小定理欧拉函数扩展欧几里得算法线性求逆元所遇到的程序开发问题。

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