乘法逆元

Kelier_pkl

·

2022-06-24 20:13:17

·

个人记录

乘法逆元

本文介绍模意义下乘法运算的逆元（Modular Multiplicative Inverse），并介绍如何使用扩展欧几里德算法（Extended Euclidean algorithm）求解乘法逆元

逆元简介

如果一个线性同余方程ax≡1(mod\ b)，则称x为a\ mod\ b的逆元，记作a^{-1}

如何求逆元

扩展欧几里得法

可适用于模数不为质数的情况

void exgcd(int a, int b, int& x, int& y) {

if (b == 0) {

x = 1, y = 0;

return;

}

exgcd(b, a % b, y, x);

y -= a / b * x;

}

扩展欧几里得法和求解线性同余方程是一个原理，在这里不展开解释。

快速幂法

只适用于模数为质数，且模数与余数互质的情况

∵$ $ax≡1(mod\ b)

∴$ $ax≡a^{b-1}(mod\ b)

∴$ $x≡a^{b-2}(mod\ b)

【理论依据：费马小定理】

然后我们就可以用快速幂来求了。

inline int qpow(long long a, int b) {

int ans = 1;

a = (a % p + p) % p;

for (; b; b >>= 1) {

if (b & 1) ans = (a * ans) % p;

a = (a * a) % p;

}

return ans;

}

递推法

可适用于模数不为质数的情况

令第i个数的逆元为inv[i]，易得：inv[i]=(p-\left\lfloor\dfrac{p}{i}\right\rfloor)×inv[p\%i]\%p

特殊情况：inv[1]=1

下面是一道例题：P3811 【模板】乘法逆元

所以代码如下：

#include

using namespace std;

typedef long long LL;

#define MAXN 3000005

LL n,p;

LL inv[MAXN];

int main(){

scanf("%lld%lld",&n,&p);

inv[1]=1;

printf("1\n");

for(LL i=2;i<=n;i++){

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

printf("%lld\n",inv[i]);

}

}