逆元
什么是逆元
在数论中，如果 \(ab \equiv 1 \pmod{p}\) ，我们就说 \(a\) 和 \(b\) 在模 \(p\) 意义下互为乘法逆元，记作 \(a = inv(b)\)。
逆元有什么用呢？
我们常常遇到一些题目要求结果对一个大质数 \(p\) 取模，这是因为答案很大，出题人为了不麻烦大家写高精，就采取这样的方法。加减法和乘法对取模运算都是封闭的，所以你可以处处取模来避免溢出。
例如：
\((\color{orange}{12} + \color{blue}{3}) \ \% \ 10 = \color{green}{5}\)
\(\color{orange}{12} \ \% \ 10 = 2\)
\(\color{blue}{3} \ \% \ 10 = 3\)
\((2 + 3) \ \% \ 10 = \color{green}{5}\)
但遇到除法时，就麻烦了：
\((\color{orange}{12} \ \div \ \color{blue}{3}) \ \% \ 10 = 4\)
\(\color{orange}{12} \ \% \ 10 = 2\)
\(\color{blue}{3} \ \% \ 10 = 3\)
\((2 \div 3) \ \% \ 10 = \ ? \ ? \ ?\)
为了解决模意义下的除法问题，我们引入了逆元。
\(\color{red}{inv(a) \ 其实可以看作模 \ p \ 意义下的 \ \frac{1}{a}}\)。
即 \(a \times inv(a) \equiv 1 \pmod{p}\)
那么在模 \(p\) 意义下， \(\frac{a}{b}\) 就可以变形为 \(a \times inv(b) \pmod{p}\)。
实际上在模 \(10\) 意义下 \(inv(3) = 7\) ，所以上面的式子可以这样计算：
\((\color{orange}{12} \div \color{blue}{3}) \ \% \ 10 = \color{green}{4}\)
\(\color{orange}{12} \ \% \ 10 = 2\)
\(\color{blue}{3} \ \% \ 10 = 3\)
\((2 \times inv(3)) \ \% \ 10 = \color{green}{4}\)
这里介绍三种计算逆元的方法：拓展欧几里得，费马小定理，线性递推。
拓展欧几里得
这个方法十分容易理解，而且对于单个查找效率似乎也还不错，比后面要介绍的大部分方法都要快(尤其对于 \(\bmod{p}\) 比较大的时候)。
这个就是利用拓欧求解线性同余方程 \(a*x \equiv c \pmod {b}\) 的 \(c=1\) 的情况。我们就可以转化为解 \(a*x + b*y = 1\) 这个方程。
这里简单讲解一下拓欧：
对于三个自然数 \(a,b,c\)，求解 \(ax+by=c\) 的 \((x,y)\) 的整数解。
首先我们要判断是否存在解，对于这个这个存在整数解的充分条件是 \(gcd(a,b) | c\)。
也就是说 \(c\) 为 \(a,b\) 最大公因数的一个倍数。
然后详细的求解过程就看这篇文章吧，点这里。
这个做法还有个好处在于，当 \(a \bot p\)（互质），但 \(p\) 不是质数的时候也可以使用。
代码比较简单：
long long exgcd(long long a, long long b, long long &x, long long &y) // 拓欧
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
long long d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
long long inv(long long a, long long p)
{
long long x, y;
if (exgcd(a, p, x, y) != 1)
return -1;
return (x % p + p) % p;
}
费马小定理
费马小定理是数论里的重要定理，叙述如下：
若 \(p\) 是质数，且 \(gcd(a, p)=1\) ，则有 \(a ^ {p - 1} \equiv 1 \pmod{p}\)
从逆元的定义推导，可得 \(a \times inv(a) \equiv 1 \equiv a ^ {p - 1} \pmod{p}\)，于是有 \(inv(a) \equiv a ^ {p - 2} \pmod{p}\)。
于是对 \(a ^ {p - 2}\) 算一下快速幂就好了。
注意这个方法只对 \(p\) 是质数的情形有效。
inline long long Pow(long long a, long long n, long long p) // 快速幂
{
long long ans = 1;
while (n)
{
if (n & 1)
ans = ans % p * a % p;
a = a % p * a % p;
n >>= 1;
}
return ans;
}
inline long long inv(long long a, long long p)
{
return Pow(a, p - 2, p);
}
线性递推
给定 \(n,p\) 求 \(1\sim n\) 中所有整数在模 \(p\) 意义下的乘法逆元。
输入保证 \(p\) 为质数，且 \(1≤n≤3×10^6，n<p<20000528\)。
如果我们要求一系列的乘法逆元，而且数据范围是 \(1 \leq n \leq 3 \times 10 ^ 6\)，常规方法是行不通的。这里介绍逆元的线性递推求法（需保证 \(p\) 是质数）。
设 \(p = aq + r\)， 即 \(q = \left\lfloor \frac{p}{a} \right\rfloor\)，\(r = p \bmod a\)。
在模 \(p\) 意义下，有 \(aq + r \equiv 0 \pmod{p}\)。
因为 \(inv(x)\) 可看作模 \(p\) 意义下的 \(\frac{1}{x}\)，
所以移项整理得 \(a = -r \times inv(q) \pmod{p}\)。
则 \(inv(a) = -q \times inv(r) \pmod{p}\)
即 \(inv(a) = -\left\lfloor \frac{p}{a} \right\rfloor \times inv(p \bmod a) \pmod{p}\)
代码实现
#include <bits/stdc++.h>
#define _ (long long)3e6 + 5
using namespace std;
long long Inv[_];
inline long long mod(long long a, long long p)
{
return (a % p + p) % p;
}
long long inv(long long a, long long p)
{
if (Inv[a] || a == 0)
return Inv[a];
Inv[a] = mod(-p / a * inv(p % a, p), p);
return Inv[a];
}
long long n, p;
signed main()
{
scanf("%lld%lld", &n, &p);
Inv[1] = 1;
for (int i = 1; i <= n; ++i)
{
printf("%lld\n", inv(i, p));
}
return 0;
}