smart_toy AI 生成摘要
本文笔记整理了乘法逆元的定义、存在条件及主要求法。介绍了基于扩展欧几里得算法的通法,以及基于费马小定理在模数为质数时的快速幂快速求解法。同时讲解了针对大规模数据需求的预处理递推方法,并强调了不同算法对模数性质的依赖,旨在帮助理解并快速查阅。
本人在比赛中经常会忘记怎么写乘法逆元,故此写下这篇笔记,方便自己和其他人查阅。
定义
如果 ,则称 为 在模 意义下的乘法逆元,记作 。
逆元的存在性条件是 和 互质,既 。
用处
乘法逆元在模 意义下的除法中起到关键作用。对于 和 ,如果我们想计算 ,可以转化为 。
求法
扩展欧几里得算法
扩展欧几里得算法可以用来求解 的整数解。对于模 的情况,我们可以设 ,则有:
根据逆元的存在条件可知 ,则有:
从而 就是 在模 意义下的乘法逆元。
代码实现
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;
}
快速幂
如果 是质数,可以使用快速幂来求逆元。根据费马小定理,对于质数 ,有:
因此:
所以可以通过快速幂计算 来得到 的逆元。
代码实现
int modInverse(int a, int p)
{
int res = 1;
a = a % p; // 确保 a 在模 p 意义下
if (a == 0) return 0; // 如果 a 为 0,则逆元不存在
int exp = p - 2; // 根据费马小定理
while (exp > 0)
{
if (exp % 2 == 1) // 如果 exp 是奇数
{
res = (res * a) % p;
}
a = (a * a) % p; // 平方
exp /= 2; // 除以 2
}
return res;
}
注意: 快速幂法使用了 费马小定理,要求 是质数,如果 不是质数,则需要使用扩展欧几里得算法。
预处理逆元
如果需要频繁计算多个数的逆元,可以预处理所有数的逆元。可以使用一个数组 inv,其中 inv[i] 存储 在模 意义下的逆元。
递推关系为:
代码实现
const int MAXN = 1000000; // 根据需要调整大小
int inv[MAXN];
void precomputeInverses(int p)
{
inv[1] = 1; // 1 的逆元是 1
for (int i = 2; i < p; ++i)
{
inv[i] = (p - p / i) * inv[p % i] % p; // 使用快速幂或扩展欧几里得算法
}
}