乘法逆元算法

63 阅读 0 评论 42 点赞

我是靠谱客的博主超帅高跟鞋，这篇文章主要介绍乘法逆元算法，现在分享给大家，希望可以做个参考。

逆元的定义

对于正整数 $a$ 和 $m$ ，如果有 $a \times x \equiv 1 (m o d m)$ ，那么就把这个同余方程中 $x$ 的最小正整数解叫做 $a$ 模 $m$ 的逆元。

根据前面的定义：对于模 $m$ ，若对于剩余类 $[a]$ ，存在剩余类 $[b]$ 使得 $[a] \times [b] = [1]$ ，则称 $[b]$ 为 $[a]$ 的逆元。记作 $a^{-1}$ 。

逆元的性质

假设存在三个剩余类 $[a], [b], [c]$ ， $[b], [c]$ 同时是 $[a]$ 的逆元，且 $[b] \neq \equiv [c] (m o d m)$ 。

则我们知道 $[b] \equiv [b] \times 1 \equiv [b] \times ([a] \times [c]) \equiv ([b] \times [a]) \times [c] \equiv [c] (m o d m)$ 。

所以它与条件相悖，故 $[b] \equiv [c] (m o d m)$ ，即我们知道，对于一个剩余类，它的逆元是唯一的。但是对于一个数，它的逆元是无穷多的。我们习惯将 $0<a^{-1}<m$ 的这个数称之为逆元。

另外，逆元具有积性： $(ab)^{-1}equiv a^{-1}times b^{-1}(mod:m)$ 。

求一个数的逆元

扩展欧几里得算法求逆元

对于 $a \times x \equiv 1 (m o d m)$ 我们可以做一个公式推导：
$a \times x \equiv 1 (m o d m)$ ;
$(a \times x - 1) % m = 0$ ;
存在一个正整数满足 $a \times x - 1 = m \times k$ ;
$a \times x - m \times k = 1$ ；
即存在 $y = - k$ 使得 $a \times x + m \times y = 1$ ;
所以求 $a$ 模 $m$ 的逆元，就是求方程式 $a \times x + m \times y = 1$ 的解，并且在实际使用中，一般把 $x$ 的最小正整数称之为 $a$ 模 $m$ 的逆元。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int n, a, b, p, x, y;
void exgcd(int a, int b){
if(b == 0){
x = 1;
y = 0;
return ;
}
exgcd(b,a%b);
int temp = x;
x = y;
y = temp - a / b * y;
}
int main(){
cin >> a >> b;
exgcd(a,b);//此时得到的x是方程的一个解，但不一定是方程的最小正整数解，x可能为负
x = (x % b + b) % b; //(x % m + m) % m 是方程最小正整数解，也就是a模m的逆元
cout << x;
return 0;
}

费马小定理求解逆元

逆元一般用扩展欧几里得算法来求解，但如果 $m$ 为素数，那么我们可以根据费马小定理得到逆元为 $a^{m-2}:mod:m$ 。

推导公式： $a^{m-1}equiv1(mod:m)=atimes a^{m-2}equiv1(mod:m)=a^{m-2}equiv frac{1}{a}(mod:m)$ 。所以 $a$ 的逆元为 $a^{p-2}$ 。从这里我们也可以看出使用费马小定理求逆元的精华就是快速幂。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef long long ll;
ll fastpow(ll n, ll a, ll mod){
if(n < 0) return 1;
ll res = 1;
a = a % mod;
while(n){
if(n & 1) res = (res * a) % mod;
a = (a * a) % mod;
n >>= 1;
}
return res % mod;
}
int main(){
cin >> a >> p;
cout << fastpow(p-2,a,p) << endl;
return 0;
}

如何求多数的逆元

线性求到的逆元

对于求很多数的逆元的题目，我们可以使用线性求解逆元。
我们先看带余除法 $p = k \times i + c$ ;
我们可以把这个式子写成 $k \times i + c \equiv 0 (m o d p)$ ;
式子两边同时乘以 $i^{-1}times c^{-1}$ ( $i^{-1},c^{-1}$ 都是模意义下的逆元)
所以我们有 $c^{-1}+i^{-1}equiv0(mod:p)$ ;
$i^{-1}equiv-ktimes c^{-1}(mod:p)$ ;
$i^{-1}equiv-(p/i)times(p%i)^{-1}(mod:p)$ ;

所以我们的 $i^{-1}$ 就可以用 $p%i)^{-1}$ 来推出，所以就可以用递推式求出来 $1$ 到 $i$ 之间所有数的逆元。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl 'n'
const int N = 3e6+10;
ll arr[N];
int main(){
ll n, p;
cin >> n >> p;
arr[1] = 1;
cout << arr[1] << endl;
for(ll i = 2; i <= n; i++){
arr[i] = (-(p / i) * arr[p % i] % p + p) % p;//防止结果为负数
cout << arr[i] << endl;
}
return 0;
}

线性求任意个数的逆元

首先，我们需要求出 $n$ 个数的前缀积，记为 $a_i$ ，然后使用快速幂或者是扩展欧几里得算法求解 $s_n$ 的逆元，记为 $arr_n$ 。因为 $arr_n$ 是 $n$ 个数的逆元，所以当我们把它乘以 $b_n$ 时，就会和 $b_n$ 的逆元相互抵消，于是就得到了 $b_i$ 到 $b_{n-1}$ 的积的逆元，记为 $arr_{n-1}$ 。同理我们可以一次计算出所有的 $arr_i$ ，于是就可以用 $a_{i-1}times arr_i$ 求得。时间复杂度为 $O(n+log_n)$ 。

如果你还是不理解我们可以使用图标的形式让你明白。

在这里插入图片描述

大家可以自行对照图标和代码推一边。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
#include <map>
using namespace std;
typedef long long ll;
#define endl 'n'
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define _for(i, a, b) for (int i=(a); i<=(b); i++)
const int INF = 0x7fffffff;
const int MAXN = 1e4 + 10;
const ll mod = 1e9 + 7;
ll n, p, b[MAXN], a[MAXN], arr[MAXN], inv[MAXN];
ll fastpow(ll n, ll a, ll p){
ll res = 1;
while(n){
if(n & 1) res = ((res % p) * (a % p)) % p;
a = ((a % p) * (a % p)) % p;
n >>= 1;
}
return res % p;
}
int main(){
cin >> n >> p;
for(int i = 1; i <= n; i++){
cin >> b[i];
}
a[0] = 1;
for(int i = 1; i <= n; i++){
a[i] = a[i - 1] * b[i] % p;
}
arr[n] = fastpow(p-2,a[n],p);
for (int i = n; i >= 1; --i) arr[i - 1] = arr[i] * b[i] % p;
for (int i = 1; i <= n; ++i) inv[i] = arr[i] * a[i - 1] % p;
for(int i= 1; i <= n; i++){
cout << inv[i] << " ";
}
return 0;
}