模意义下的数论

基础知识

拉格朗日定理：在模 $p$ 意义下，最高次项系数非 $0$ 的 $n$ 次多项式至多有 $n$ 个根。

线性同余方程组

可以使用 CRT 解决模数互质的情况，exCRT 解决模数不互质的情况。

$$\begin{cases} x\equiv a_1 \pmod {m_1}\\ x\equiv a_2 \pmod {m_2}\\ \cdots\\ x\equiv a_3 \pmod {m_3}\\ \end{cases}$$

模数互质

设 $M=\prod_{i=1}^{n}m_i,M_i=m\div m_i$，$t_i$ 是线性同余方程 $M_it_i\equiv 1 \pmod{m_i}$ 的一个解，也就是说 $t_i$ 是 $M_i$ 模 $m_i$ 的逆元（显然 $M_i \perp m_i$ 当且仅当 $m_i$ 两两互质），那么 $x=\sum_{i=1}^{n}a_iM_it_i + kM$，最小非负整数解需要求 $\sum_{i=1}^{n}a_iM_it_i\bmod M$。

1
2
3
4
5
6
7
8
9
10

i64 CRT(void) {
    // x === a[i] (mod m[i])
    i64 ans = 0, x;
    for (int i = 1; i <= n; ++i) {
        M[i] = mm / m[i]; 
        t[i] = inv(M[i], m[i]); 
        ans = (ans + a[i] * M[i] * t[i]) % mm;
    }
    return (ans % mm + mm) % mm; 
}

模数不互质

考虑如何合并两个方程组。我们先假定一定可以合并，然后看看什么时候合并之后的解是 $\varnothing$。

假设我们有：

$$\begin{cases} x\equiv a \pmod A\\ x\equiv b \pmod B \end{cases}$$

那么 $x=Ak_1+a=Bk_2+b$，不难使用 exgcd 求出一组合法的 $k_1,k_2$，则通解为：

$$K_1=k_1+t\times \frac{B}{\gcd(A,B)}\\ K_2=k_2-t\times \frac{A}{\gcd(A,B)}$$

则 $x=A(k_1+t\times \frac{B}{\gcd(A,B)})+a=Ak_1+t\times \operatorname{lcm}(A,B)+a$，也就是：

$$x\equiv Ak_1+a \pmod{\operatorname{lcm}(A,B)}$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14

i64 exCRT(void) {
    // x === A[i] (mod B[i])
    i64 A = 1;
    LL a = 0; // M 为当前合并的模数，ans 为当前答案
    for (int i = 1; i <= n; ++i) {
        i64 b = ::A[i], B = ::B[i], x, y, c = b - a;
        i64 g = exgcd(A, B, x, y);
        if (c % g != 0) return -1;
        a = A * ((LL)x * (c / g)) + a;
        A = A / g * B;
        a %= A;
    }
    return (a + A) % A;
}