逆元简介
逆元简介
Claire0918
·
2023-05-31 19:28:54
·
学习·文化课
逆元（也称乘法逆元、逆），是一种特殊运算，需要一个参与运算的正整数 a 和一个模数（通常为定值）p。
当 ax \equiv 1 \pmod p 时，我们称 x 为 a 在模 p 意义下的逆元（也称 a 的逆元），通常记作 a^{-1}。
细读定义，我们会发现，若 x 有解，则其必有无数个解；否则，x 无解。因此，我们规定：所有 x 只考虑在 [1, p) \cap \mathbb{Z} 中的解。
逆元的作用
由逆元定义可知，\forall (a, b, p \in \mathbb{N}_+, \frac{a}{b} \in \mathbb{Z}), \frac{a}{b} \equiv a \cdot b^{-1} \pmod p，读者自证不难。
利用这个结论，我们可以在 C++ 等语言中限制中间结果的大小。
逆元基本定理
若 \gcd(a, p) \neq 1，x 无解。
下面给出证明：
首先，我们知道：对于任意两个正整数，若其二者差为 1，则其二者必互质。此记作定理一。
我们假设 a 和 p 不互质，则对于任意 x \in [1, p) \cap \mathbb{Z}，ax 与 p 不互质。
又由定理一，由于 ax \equiv 1 \pmod p，所以 ax 与 p 互质。
与假设矛盾，故假设不成立，x 无解。\square
如何求一个数的逆元
下文可能涉及部分 C++ 及算法知识，无基础可以只看数学推导。
求一个数 a 的逆元一般有三种方法，分别有其适用范围。
费马小定理与快速幂
此方法要求 p 为质数
费马小定理：\forall (a \in \mathbb{Z}, p \in \mathbb{P}), a^{p - 1} \equiv 1 \pmod p。
由其进行推导，可得 ax \equiv a^{p - 1} \pmod p。
由同余的性质，可得 x \equiv a^{p - 2} \pmod p。
由于 x 的定义，此式中取模后的 x 即是逆元的解。
使用快速幂，时间复杂度 \mathcal{O}(\log_2 p)。
Code:
#include
#define mem(a, v) memset(a, v, sizeof(a));
using namespace std;
typedef long long ll;
ll a, p;
inline ll quick_pow(ll a, ll b){
ll res = 1;
while (b){
if (b & 1){
res = res * a % p;
}
a = a * a % p;
b >>= 1;
}
return res;
}
int main(){
scanf("%lld %lld", &a, &p);
printf("%lld", quick_pow(a, p - 2));
return 0;
}
扩展欧几里得（扩欧）
此方法通用。
前置知识：扩展欧几里得。
扩欧原式为 ax + by = \gcd(a, b)，求 x 和 y。
逆元原式 ax \equiv 1 \pmod p 可以表示为 ax + py = 1 的形式，可以用扩欧求解。
求得 x 后再按照逆元定义将其处理即可。
时间复杂度 \mathcal{O}(\log_2 a)。
Code:
#include
#define mem(a, v) memset(a, v, sizeof(a));
using namespace std;
typedef long long ll;
ll a, p, x, y;
inline ll exgcd(ll a, ll b, ll &x, ll &y){
ll d = a;
if (!b){
x = 1, y = 0;
}else{
d = exgcd(b, a % b, y, x);
y -= a / b * x;
}
return d;
}
int main(){
scanf("%lld %lld", &a, &p);
exgcd(a, p, x, y);
printf("%lld", (x + p) % p);
return 0;
}
逆元递推式
此方法要求 1 至 a 间的所有整数的逆元都有解。
对于 a，现在已知 1 至 a - 1 间所有整数的逆元，现在要求 a 的逆元。
令 i = \lfloor \frac{p}{a} \rfloor，j = p \bmod a。
则有 a \cdot i + j = p，可转化为 a \cdot i + j \equiv 0 \pmod p。
恒等式两侧同时乘 a^{-1} \cdot j^{-1}，可得 a \cdot a^{-1} \cdot i \cdot j^{-1} + j \cdot a^{-1} \cdot j^{-1} \equiv 0 \pmod p，可化为 i \cdot j^{-1} + a^{-1} \equiv 0 \pmod p。
移项，可得 a^{-1} \equiv -i \cdot j^{-1} \pmod p，即 a^{-1} = |p - i \cdot j^{-1}|。
代入，可得 a^{-1} = |p - \lfloor \frac{p}{a} \rfloor \cdot (p \bmod a)^{-1}|。
又 1^{-1} = 1，可以用类似数学归纳法（迭代）的方法求解 a^{-1}。
时间复杂度 \mathcal{O}(a)，远不及前两种方法，但由于其预处理的实现方式，使其在多次查询时可以达到均摊 \mathcal{O}(1) 的复杂度。
代码请读者按照推导自行实现。