乘法逆元算法

逆元的定义

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

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

逆元的性质

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

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

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

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

求一个数的逆元

扩展欧几里得算法求逆元

对于$a\times x\equiv 1(modm)$我们可以做一个公式推导：
$a\times x\equiv 1(modm)$;
$(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$的逆元。

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}modm$。

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

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(modp)$;
式子两边同时乘以$i^{-1}\times c^{-1}$($i^{-1},c^{-1}$都是模意义下的逆元)
所以我们有$k\times c^{-1}+i^{-1}\equiv 0(modp)$;
$i^{-1}\equiv -k\times c^{-1}(modp)$;
$i^{-1}\equiv -(p/i)\times (p\%i{)}^{-1}(modp)$;

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

#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$的逆元，记为$ar{r}_n$。因为$ar{r}_n$是$n$个数的逆元，所以当我们把它乘以$b_n$时，就会和$b_n$的逆元相互抵消，于是就得到了$b_i$到$b_{n-1}$的积的逆元，记为$ar{r}_{n-1}$。同理我们可以一次计算出所有的$ar{r}_i$，于是就可以用$a_{i-1}\times ar{r}_i$求得。时间复杂度为$O(n+lo{g}_n)$。

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

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

#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;
}

最后

以上就是超帅高跟鞋为你收集整理的乘法逆元算法的全部内容，希望文章能够帮你解决乘法逆元算法所遇到的程序开发问题。

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