乘法逆元小结

参考自：点击此处

乘法逆元，一般用于求（a / b）(modp)的值（p 通常为质数），是解决模意义下分数数值的必要手段。
关于求余，有以下三种规则：
加法：(a+b)%m=(a%m+b%m)%m(a+b)%m=(a%m+b%m)%m
减法：(a−b)%m=(a%m−b%m)%m(a−b)%m=(a%m−b%m)%m
乘法：(a∗b)%m=(a%m∗b%m)%m(a∗b)%m=(a%m∗b%m)%m
但是这个规则在除法不适用，所以就要用到乘法逆元。

逆元的定义

若a ∗ x = 1 ( mod b )，且 a 与 b 互质，那么我们就能定义:x 为 a 的逆元，记为a−1
所以我们也可以称 x 为 a 在 mod b 意义下的倒数，
进而对于 a / b ( mod p ) ，我们可以求出 b 在 mod p 下的逆元，然后乘上 a ，再 mod p，就是要求的值了。

求解逆元的方法

1. 快速幂

想要了解快速幂的知识请点此处
时间复杂度：O(log n)
要利用到费马小引理:

若p为素数，a为正整数，且a、p互质
则有a ^ (p − 1) = 1 ( mod p )。

这个我们就可以发现它这个式子右边刚好为 1 。
所以我们就可以放入原式，就可以得到：
a ∗ x = 1 ( mod p )
a ∗ x = a ^ (p − 1) ( mod p )
x = a ^ (p − 2) ( mod p )
所以我们可以用快速幂来算出 a ^ (p - 2) ( mod p ) 的值，这个数就是a在mod p下的逆元了

测试代码

#include <iostream>
#include <cstdio>
using namespace std;
#define ll long long
ll quick_pow(ll x, ll n, ll mod)
{
ll res = 1;
while (n > 0)
{
if (n % 2 == 1)
{
res *= x % mod;
}
x *= x % mod;
n >>= 1;
}
return res;
}
int main(void)
{
ll a, p;
ll x = quick_pow(a, p - 2, p);
x = (x % p + p) % p; //x为a在mod p意义下的逆元
printf("%lldn", x);
return 0;
}

2.拓展欧几里得

时间复杂度：O(log n)
这个方法十分容易理解，而且对于单个查找效率似乎也还不错，比大部分方法都要快(尤其对于 mod p 比较大的时候)。
这个就是利用拓欧求解 线性同余方程 a ∗ x = c (mod b) 的c = 1的情况。我们就可以转化为解 a ∗ x + b ∗ y = 1 这个方程。求解这个方程的解。不会拓欧可以点这里~
好处：当 a⊥p （互质），但 p 不是质数的时候也可以使用。

测试代码

#include <iostream>
#include <cstdio>
using namespace std;
#define ll long long
void Exgcd(ll a, ll b, ll &x, ll &y)
{
if (!b)
x = 1, y = 0;
else
Exgcd(b, a % b, y, x), y -= a / b * x;
}
int main(void)
{
ll x, y;
ll a, p;
scanf("%lld%lld", &a, &p);
Exgcd (a, p, x, y);
x = (x % p + p) % p; // x为a在mod p意义下的逆元
printf("%lldn", x);
return 0;
}

3.线性算法

用于求一连串数字对于一个 mod p 的逆元
并且大多数题只能用这种方法，别的算法都比这些要求一串要慢。

首先我们有一个,1^(−1) = 1 (mod p)
然后设 p = k ∗ i + r, (1 < r < i < p) 也就是 k 是 p/i 的商，r 是余数 。
再将这个式子放到(mod p)意义下就会得到：
k ∗ i + r = 0(mod p)
然后乘上i ^ (-1), r ^ (−1)就可以得到:
k ∗ r − 1 + i − 1 = 0(mod p)
i ^ (-1) = (−k) ∗ r − 1 (mod p)
i ^ (-1) = − ⌊p / i⌋ ∗ (p mod i) ^ (-1) (mod p)
然后，我们就可以从前面推出当前的逆元了。

例题

洛谷P3811

AC代码

#include <iostream>
#include <cstdio>
using namespace std;
#define ll long long
const int MX = 3e6 + 5;
ll
inv[MX] = {0}; // 不用ll会溢出 
int main(void)
{
int n, p;
scanf("%d%d", &n, &p);
inv[1] = 1;
for (int i = 2; i <= n; ++ i)
{
inv[i] = (p - p/ i) * inv[p % i] % p;
}
for (int i = 1; i <= n; ++ i)
{
if(i != 1)
{
printf("n");
}
printf("%d", inv[i]);
}
return 0;
}

最后

以上就是苹果香烟为你收集整理的乘法逆元的三种求解方法乘法逆元小结的全部内容，希望文章能够帮你解决乘法逆元的三种求解方法乘法逆元小结所遇到的程序开发问题。

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