拓展中国剩余定理 exCRT

标签：剩余 frac int 定理 exCRT 1k mod inv equiv

求解如下形式的一元线性同余方程组（其中 \(n_1, n_2, ···, n_k\) 不 两两互质）

\[\left\{ \begin{matrix}x & \equiv & a_1 & (mod \ n_1)\\ x & \equiv & a_2 & (mod \ n_2)\\ \vdots\\ x & \equiv & a_k & (mod \ n_k)\end{matrix} \right. \]

• 推导：从简单入手，先考虑同于方程组只有两个式子的情况

\[x\equiv c_1\ (mod\ m_1) \]

\[x\equiv c_2\ (mod\ m_2) \]

变形：

\[x = c_1 + m_1k_1 \]

\[x = c_2 + m_2k_2 \]

联立：

\[c_1 + m_1k_1 = c_2 + m_2k_2 \]

移项：

\[m_1k_1 = c_2 - c_1 + m_2k_2 \]

用 \((a, b)\) 表示 \(a\) 和 \(b\) 的最大公约数。
方程有解的条件为 \((m_1, m_2)|(c_2-c_1)\).
对于上面的方程，两边同除 \((m_1,m_2)\)

\[\frac{m_1k_1}{(m_1,m_2)}=\frac{(c_2-c_1)}{(m_1,m_2)}+\frac{m_2k_2}{(m_1,m_2)} \]

转换：

\[\frac{m_1}{(m_1,m_2)}k_1\equiv\frac{c_2-c_1}{(m_1,m_2)}(mod\ \frac{m_2}{(m_1,m_2)}) \]

同余式两边同除 \(\frac{m_1}{(m_1,m_2)}\)

\[k_1\equiv inv(\frac{m_1}{(m_1,m_2)},\frac{m_2}{(m_1,m_2)})×\frac{(c_2-c_1)}{(m_1,m_2)}(mod\ \frac{m_2}{(m_1,m_2)}) \]

\[k_1 = inv(\frac{m_1}{(m_1,m_2)},\frac{m_2}{(m_1,m_2)})×\frac{(c_2-c_1)}{(m_1,m_2)}+ \frac{m_2}{(m_1,m_2)} × y \]

\(inv(a, b)\) 表示 \(a\) 在模 \(b\) 意义下的逆元。
将 \(k_1\) 代入 \(x = c_1 + m_1k_1\)
得：

\[x = inv(\frac{m_1}{(m_1,m_2)},\frac{m_2}{(m_1,m_2)})×\frac{(c_2-c_1)}{(m_1,m_2)} × m_1 + \frac{m_1m_2}{(m_1,m_2)} × y + c_1 \]

\[x \equiv inv(\frac{m_1}{(m_1,m_2)},\frac{m_2}{(m_1,m_2)})×\frac{(c_2-c_1)}{(m_1,m_2)} × m_1 + c_1 \ (mod\ \frac{m_1m_2}{(m_1,m_2)}) \]

推广一下

我们每次把两个同余式合并，求解之后得到一个新的同余式。再把新的同余式和其他的联立，最终就可以求出满足条件的解。

【模板】扩展中国剩余定理（EXCRT）

code

const int N = 1e5 + 10;

int n, M[N], C[N];

int gcd(int a, int b)
{
    return !b ? a : gcd(b, a % b);
}

int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int inv(int a, int b)
{
    int x, y;
    exgcd(a, b, x, y);
    return x < 0 ? x += b : x;
}

int main()
{
    rd(n);
    for (int i = 1; i <= n; i ++ )
        rd(M[i]), rd(C[i]);
    bool flag = 1;
    for (int i = 2; i <= n; i ++ )
    {
        int M1 = M[i - 1], M2 = M[i], C1 = C[i - 1], C2 = C[i], t = gcd(M1, M2);
        if ((C2 - C1) % t != 0)
        {
            flag = 0;
            break;
        }
        M[i] = (M1 * M2) / t;
        C[i] = (inv(M1 / t, M2 / t) * (C2 - C1) / t) % (M2 / t) * M1 + C1;
        C[i] = (C[i] % M[i] + M[i]) % M[i];
    }
    if (flag)
        print(C[n]);
    else puts("");
    return 0;
}

标签：剩余,frac,int,定理,exCRT,1k,mod,inv,equiv
From： https://www.cnblogs.com/kroyosh/p/16611625.html