数学之逆元
lml0928
·
2023-11-05 16:21:07
·
算法·理论
先来点定义
定义 a 在模 p 意义下的逆元为：同余方程
ax \equiv 1 \pmod p
的解 x。在本文中，将 a 的逆元简记为 a^{-1}。\
如果 p 是质数，那么一定有且只有一个解 x。
注：本文中所有数为整数。
如何求逆元？
1. 对一个数求逆元
我们使用 O(\log(p)) 的做法来解决。
从费马小定理可得：
a^{p-2} \times a \equiv 1 \pmod p
在 p 为素数时对任意 a 都成立。
也即，a^{p-2} = a^{-1}。使用快速幂即可将时间复杂度优化为 O(\log(p))。
但是，如果 p 不是质数，那么就不能用这种方法。但是，我们可以使用扩展欧几里得。具体详解：扩展欧几里得
首先，我们需要解的方程是 ax \equiv 1 \pmod p。
消去模运算，得 ax + pk = 1。\
不难发现，这是一个二元一次不定方程模型，可以用扩展欧几里得找到一组特解。
这里可能有人会问：扩展欧几里得解的不是 ax+by=\gcd(a,b) 吗，怎么右边是 1？
考虑裴蜀定理。如果 ax + pk = 1 有解，那么就有 \gcd(a,p) \mid 1，也即 \gcd(a,p)=1，所以方程等价于 ax+pk=\gcd(a,p)。
但是，我们并不想要这种任意解。我们要一个 1 \le x
这里有一个规律：如果一个二元一次不定方程有一组解 (x,y)，当 (a,b) 互质时，它的通解为 (x+kb,y-ka)。
这里给出充分性的证明：
&= ax+by\\
&=c
\end{aligned}
必要性的证明留给读者。主要是我不会（（（
模板题：
解析：
首先根据题意，投中一个三分球的概率为 \dfrac{a}{b}。所以连续投中三个三分球的概率为 (\dfrac{a}{b})^3，即 \dfrac{a^3}{b^3}。所以这题的答案即为 a^3 * (b^3)^{-1}，使用逆元模板计算即可。
代码：（这里只给出快速幂版本，扩欧模版改一下就好了，在扩欧的文章里）
#include
using namespace std;
const int P = (int)1e9 + 7;
int Fastpow(int a, int b)
{
int res = 1, x = a;
while(b > 0)
{
if(b & 1) res = (1ll * res * x) % P;
x = (1ll * x * x) % P;
b /= 2;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int a, b;
cin >> a >> b;
a *= a * a, b *= b * b;
cout << (1ll * a * Fastpow(b, P - 2)) % P;
return 0;
}
再补充一道例题 ：ABC326E
2. 线性递推求 1 \sim p-1 的逆元
这种题目一般有多组数据，模数比较小，而且卡带 \log 的程序这三种特点。
此时方法 1 会 TLE，我们需要使用逆元的线性递推。
递推的起始条件为 1^{-1} \equiv 1 \pmod p，显然对任何质数 p 都成立。
现在要求 i^{-1}，并假设已经求出了 1 \sim i - 1 的逆元。
首先，设 p = q \times i + r。那么，q = \lfloor \dfrac{p}{i} \rfloor，r = p \bmod i。
也即：
q \times i + r \equiv 0 \pmod p
两边同乘以 i^{-1} \times r^{-1}：
q \times r^{-1} + i^{-1} \equiv 0 \pmod p
我们看到了要求的 i^{-1}，所以将剩余部分移到右边：
i^{-1} \equiv r^{-1} \times (-q) \pmod p
将 q 和 r 用 p 表达，得：
i^{-1} \equiv (p \bmod i)^{-1} \times (p - \lfloor \dfrac{p}{i} \rfloor) \pmod p
于是，我们直接递推即可。
模板题：
P3811
解析：裸的模板。
代码：
#include
using namespace std;
int inv[3000010];
int main()
{
int n, p;
scanf("%d%d", &n, &p);
inv[1] = 1;
puts("1");
for(int i = 2; i <= n; i++)
{
inv[i] = (p - p / i) * 1ll * (inv[p % i]) % p;
printf("%d\n", inv[i]);
}
return 0;
}