「洛谷 P4777」拓展中国剩余定理 - 数论

发表于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

给定 \(n\) 组非负整数 \(a_i, b_i\) ，求解关于 \(x\) 的方程组的最小非负整数解。 \[\begin{cases} x \equiv b_1\ ({\rm mod}\ a_1) \\ x\equiv b_2\ ({\rm mod}\ a_2) \\ ... \\ x \equiv b_n\ ({\rm mod}\ a_n)\end{cases}\]

解题思路

本题的 \(a_1, a_2, \cdots, a_n\) 并不互质，故无法使用中国剩余定理。所以我们需要使用其他方法解决该问题。

多个方程不好分析，我们可先分析前两个方程。这两个方程转化如下（\(c, d \in \mathbb{Z}\)）：

\[ \begin{cases} x \equiv b_1 \pmod {a_1} \\ x \equiv b_2 \pmod {a_2} \end{cases} \Rightarrow \begin{cases} x = ca_1 + b_1 \\ x = da_2 + b_2 \end{cases} \]

将两式联立，我们可得出 \(ca_1 + b_1 = da_2 + b_2\)，转化可得 \(a_1c - a_2d = b_2 - b_1\)，这个方程显然可用拓展欧几里得解决，且可得当 \(\gcd(a_1, a_2) \nmid (b_2 - b_1)\) 时无解。

设我们得到的解为 \(c, d\)，于是我们带入可得 \(x = ca_1 + b_1\) 为其中的一个特殊解，故我们可得 \(x \equiv ca_1 + b_1 \pmod {\operatorname{lcm}(a_1, b_1)}\)。这样我们就可把前两个方程合并为同一个方程。以此类推将方程两两合并即为答案。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>

typedef __int128 ll;
const int MAXN = 1e5;

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

ll excrt(int n, ll a[], ll m[]) {
    ll na = a[1], nm = m[1];
    for (int i = 2; i <= n; i++) {
        ll p, q;
        ll d = exgcd(nm, m[i], p, q);
        p *= (na - a[i]) / d, q *= (na - a[i]) / d;
        nm = nm / d * m[i];
        na = (a[i] + q * m[i] % nm) % nm;
    }

    ll p, q;
    exgcd(1, nm, p, q);
    return ((p * na) % nm + nm) % nm;
}

int main() {
    int n;
    scanf("%d", &n);

    static ll a[MAXN + 1], m[MAXN + 1];
    for (int i = 1; i <= n; i++) {
        long long ta, tm;
        scanf("%lld %lld", &tm, &ta);
        a[i] = ta, m[i] = tm;
    }

    printf("%lld\n", (long long)excrt(n, a, m));

    return 0;
}