中国剩余定理（CRT）——数学中中国人的骄傲

· · 题解

又来写题解了。

中国剩余定理（CRT）

也称中国单身狗定理。

这个定理其实就是让你求一个同余方程组的解，具体内容如下：

设 m_1,m_2,m_3,...,m_n 是两两互质的整数，设 M=\prod\limits_{i=1}^{n}m_i，m'_i=\frac{M}{m_i}，t_i 是线性同余方程 m_i't_i\equiv1(\text{mod}\ m_i) 的一个解，对于任意 n 个整数 a_1,a_2,a_3,...,a_n，方程组

x\equiv a_1\pmod {m_1}\\ x\equiv a_2\pmod {m_2}\\ x\equiv a_3\pmod {m_3}\\ \cdot\cdot\cdot\\ x\equiv a_n\pmod {m_n}\\ \end{cases}

有整数解，解为 x=\sum\limits_{i=1}^{n}a_im_i't_i。

证明：

因为 m'_i=\frac{M}{m_i}，也就是说对于 \forall k\ne i 都有 a_im_i't_i\equiv0\pmod {m_k}。又因为 a_im_i't_i\equiv a_i\pmod {m_i}，代入原方程组可得 x=\sum\limits_{i=1}^{n}a_im_i't_i。

证毕。

而本题其实就是给出 n 个同余方程，将它们组成同余方程组，然后用 CRT 解决这个问题。具体过程就按照证明步骤一步一步来就行了。

Code：

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int N = 1e6 + 15, inf = 1e9 + 7;

const bool I_LOVE_CCF = true;

int n;
int a[N], b[N], m = 1;
int M[N], t[N];

inline int read (int &n) {
    int x = 0, f = 1;
    char ch = getchar ();
    while (! isdigit (ch)) {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (isdigit (ch)) {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar ();
    }
    n = x * f;
    return n;
}

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

int mul (int a, int b, int mod) {
    int ans = 0;
    while (b) {
        if (b & 1) ans = (ans + a) % mod;
        b >>= 1;
        a = (a + a) % mod;
    }
    return ans % mod;
}

int quick_power (int a, int b, int mod) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = (ans * a + mod) % mod;
        b >>= 1;
        a = (a * a + mod) % mod;
    }
    return ans % mod;
}

int CRT () {
    rep (i, 1, n) M[i] = m / a[i];
    rep (i, 1, n) {
        int y;
        exgcd (M[i], a[i], t[i], y);
        t[i] = (t[i] % a[i] + a[i]) % a[i];
    }
    int ans = 0;
    rep (i, 1, n) {
        ans = (ans + mul (mul (b[i], M[i], m), t[i], m));
    }
    return ans % m;
}

signed main () {
    read (n);
    rep (i, 1, n) read (a[i]), read (b[i]), m *= a[i];
    printf ("%lld\n", CRT ());
    return 0;
}