线性同余方程
定义
形如 \(ax \equiv c \pmod b\) 的方程被称为 线性同余方程(Congruence Equation)。
求解方式
定理 1
方程 \(ax+by=c\) 与方程 \(ax \equiv c \pmod b\) 是等价的，有整数解的充要条件为 \(\gcd(a,b) \mid c\)。
根据定理 \(1\) ，方程 \(ax+by=c\)，我们可以先用扩展欧几里得算法求出一组 \(x_0,y_0\)，也就是
两边同时除以 \(\gcd(a,b)\)，
乘以 \(c\) ，得到
然后就找到了方程的一个解。
定理 2
若 \(\gcd(a,b)=1\)，且 \(x_0\)、\(y_0\) 为方程 \(ax+by=c\) 的一组解，则该方程的任意解可表示为：
且对任意整数 \(t\) 都成立。由此即可以求出方程的所有解。
但在实际问题中，我们往往被要求求出一个最小整数解，也就是一个特殊解
其中 \(t=\dfrac{b}{\gcd(a,b)}\)。
代码：
int ex_gcd(int a, int b, int &x, int &y)
{
if (!b)
{
x = 1;
y = 0;
return a;
}
int t = ex_gcd(b, a % b, x, y);
int tmp = x;
x = y;
y = tmp - a / b * y;
return t;
}
bool liEu(int a, int b, int c, int &x, int &y)
{
int t = ex_gcd(a, b, x, y);
int k = c / t;
if (c % t != 0)
return false;
x *= k;
y *= k;
return true;
}
逆元
定义
逆元（素），是指一个可与取消另一个元素运算的元素。数学中逆元有加法逆元和乘法逆元（乘法中的倒数）
本篇文章只介绍乘法逆元。/dk
乘法逆元
-
\(\pmod P\) 意义下，一个数 \(a\) 如果有逆元 \(x\) ，那么除以 \(a\) 相当于乘以 \(x\)
（进化版 \(\cfrac{1}{a}\) ？） -
\(\pmod P\) 意义下， \(a\) 存在逆元的充要条件事 \(p \ne 1\) ，且 \(a\) 与 \(p\) 互质
计算逆元
拓展欧几里得
不难得出，\(ax \equiv c \pmod b\) 等价于 \(a \times x + b \times y = c\) ，那么显然当 \(\gcd(a,b) \ne 1\) 时，上述方程无解。
也就是说，使得 \(a \times x + b \times y = c\) 有解的充要条件是 \(c \% \gcd(a, b) =0\) 。
一般情况下，上式能够计算出无数组合法解，但是题目往往要求计算出最小的那组解。我们可以首先求出一个特殊解 \(x_0\) ，那么最小的解便是 \(x_0 \% b\)。
正确性？
首先，\(x\) 的通解是 \(x_0 + b \times t\) 吗？
那么，也就是说， \(a\) 关于 \(b\) 的逆元是一个关于 \(m\) 同余的，那么根据最小整数原理，一定存在一个最小的正整数，它是 \(a\) 关于 \(b\) 的逆元，而最小的肯定是在\((0 , b)\) 之间的，而且只有一个，这就好解释了。
当 \(b\) 是负数的时候，我们取 \(b\) 的绝对值就行了，当 \(x_0\) 是负数的时候，他模上 \(b\) 的结果仍然是负数（在计算机计算的结果上是这样的，虽然定义的时候不是这样的），这时候，我们仍然让 \(x_0\) 对 abs(b) 取模，然后结果再加上 abs(b) 就行了，于是，我们不难写出下面的代码求解一个数 \(a\) 对于另一个数 \(b\) 的乘法逆元：
int cl(int a, int b)
{
int x, y;
int t = ex_gcd(a, b, x, y);
if (1 % t != 0)
return -1;
x *= 1 / t;
int ans = x % abs(b);
if (ans <= 0)
ans += abs(b);
return ans;
}
快速幂法
因为 \(ax \equiv 1 \pmod b\)，
又由费马小定理可得 \(ax \equiv a^{b-1} \pmod b\) ，
所以 \(x \equiv a^{b-2} \pmod b\)。
代码：
int Qpow(int a, int b)
{
int ans = 1;
a = (a % p + p) % p;
while (b)
{
if (b & 1)
ans = (a * ans) % p;
a = (a * a) % p;
b >>= 1;
}
return ans;
}
线性求逆元
求出 \(1,2,...,n\) 中每个数关于 \(p\) 的逆元。
显然有 \(1^{-1} \equiv 1 \pmod p\)。
证明：
对于 \(\forall p \in \mathbf{Z}\)，有 \(1 \times 1 \equiv 1 \pmod p\) 恒成立，故在 \(p\) 下 \(1\) 的逆元是 \(1\)。
其次对于递归情况 \(i^{-1}\)，令 \(k = \lfloor \frac{p}{i} \rfloor\)，\(j = p \bmod i\)，有 \(p = ki + j\)。
则有
两边同时乘 \(i^{-1} \times j^{-1}\)
代入 \(j = p \bmod i\)
又有
由于 \(p \bmod i < i\)，则在迭代中我们完全可以假设我们已经知道了所有的模 \(p\) 下的逆元 \(j^{-1}, j < i\)。
故我们就可以推出逆元，利用递归的形式，而使用迭代实现：
代码：
inv[1] = 1;
for (int i = 2; i <= n; ++i)
{
inv[i] = (p - p / i) * inv[p % i] % p;
}
通过 \(p-\lfloor \cfrac{p}{i} \rfloor\) 来防止出现负数。
另外，根据线性求逆元方法的式子
递归求解 \(j^{-1}\), 直到 \(j=1\) 返回 \(1\)。
其实还可以利用记忆化来避免多次递归导致的重复，但是这样求 \(1,2,...,n\) 中所有数的逆元的时间复杂度仍是 \(O(n)\)。
线性同余方程、逆元 完结！！