中国剩余定理（Chinese remainder theorem）

内容

对于以下一元线性同余方程组：
(S): \begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_n \pmod{m_n} \end{cases}
其中整数m_1, m_2, \ldots, m_n两两互质，则对于任意的整数a_1, a_2, \ldots, a_n，方程组 (S) 有解，并且可以用如下方式构造解：

1. 设M=\prod_{i=1}^n m_i，M_i = \frac{M}{m_i}
2. 设M_i^{-1}为M_i模m_i意义下的逆元，即M_iM_i^{-1} \equiv 1 \pmod{m_i}
3. 该方程组的通解为x = kM + \sum_{i=1}^n a_iM_iM_i^{-1} \ (k \in \mathbb{Z})。在模M意义下，该方程组的唯一解为x = \sum_{i=1}^n a_iM_iM_i^{-1}。

例题：中国剩余定理 问题 – 51Nod

按照上述方式构造解即可。代码如下。

// Code by KSkun, 2018/4
#include <cstdio>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 20;

int n, p[MAXN], m[MAXN];

inline LL fpow(LL n, LL k, LL p) {
    LL res = 1;
    while(k) {
        if(k & 1) res = res * n % p;
        n = n * n % p;
        k >>= 1;
    }
    return res;
}

inline LL crt() {
    LL pall = 1, res = 0;
    for(int i = 1; i <= n; i++) {
        pall *= p[i];
    }
    for(int i = 1; i <= n; i++) {
        res = (res + m[i] * pall / p[i] % pall 
            * fpow(pall / p[i], p[i] - 2, p[i]) % pall) % pall;
    }
    return res;
}

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        p[i] = readint(); m[i] = readint();
    }
    printf("%lld", crt());
    return 0;
}

扩展中国剩余定理（exCRT）

内容

对于CRT的扩展适用于CRT模数非互质的情况。
我们来研究两个同余方程的情况：
\begin{cases} x \equiv b_1 \pmod{a_1} \\ x \equiv b_2 \pmod{a_2} \end{cases} \Rightarrow \begin{cases} x = a_1x_1 + b_1 \\ x = a_2x_2 + b_2 \end{cases}
我们可以联立后面的展开式，得到这个式子a_1x_1 + a_2x_2 = b_2 - b_1。这个式子有解的条件是\mathrm{gcd}(a_1, a_2) | (b_2 - b_1)，如果有解，我们可以利用扩展欧几里得算法（欧几里得算法和扩展欧几里得算法 | KSkun’s Blog）求出x_1的一个解（实际上求出的是方程a_1x_1 + a_2x_2 = \mathrm{gcd}(a_1, a_2)的解，需要转换，即乘一个\frac{b_2-b_1}{\mathrm{gcd}(a_1, a_2)}），回代可以得到x的一个解x'。
这时，我们可以用这个方程x \equiv x' \pmod{\mathrm{lcm}(a_1, a_2)}代替原来的两个方程。
我们可以每次合并两个方程，最终得到一个同余方程，就可以求解了。

例题：2891 — Strange Way to Express Integers

直接利用上述方法解决即可。代码如下。

// Code by KSkun, 2018/4
#include <cstdio>

typedef long long LL;

const int MAXN = 100005;

LL k, a[MAXN], r[MAXN];

inline LL exgcd(LL a, LL b, LL &x, LL &y) {
    if(!b) {
        x = 1; y = 0; return a;
    }
    LL res = exgcd(b, a % b, x, y);
    LL t = x; x = y; y = t - a / b * y;
    return res;
}

inline LL excrt() {
    LL A = a[1], R = r[1], x, y;
    for(int i = 2; i <= k; i++) {
        LL g = exgcd(A, a[i], x, y);
        if((r[i] - R) % g) return -1;
        x = (r[i] - R) / g * x; x = (x % (a[i] / g) + a[i] / g) % (a[i] / g);
        R = A * x + R;
        A = A / g * a[i]; R %= A;
    }
    return R;
}

int main() {
    while(scanf("%lld", &k) != EOF) {
        for(int i = 1; i <= k; i++) {
            scanf("%lld%lld", &a[i], &r[i]);
        }
        printf("%lld\n", excrt());
    }
    return 0;
}

参考资料

• 中国剩余定理 – 维基百科，自由的百科全书
• 51nod1079(中国剩余定理) – geloutingyu – 博客园
• 中国剩余定理学习笔记 – MashiroSky – 博客园
• 中国剩余定理与扩展 – CSDN博客
• 《算法竞赛入门经典 训练指南》，刘汝佳，陈锋著，清华大学出版社，9787302291077