形式化题目

给定 $n$ 个两两互质的正整数 $a_1, a_2, \dots, a_n$ 与对应的余数 $b_1, b_2, \dots, b_n$，求满足

的最小正整数 $x$。由于 $a_i$ 两两互质，解在模 $\prod_{i=1}^{n} a_i$ 意义下唯一。

题面中的「建了 $a_i$ 个猪圈，剩下 $b_i$ 头猪没有去处」说的正是 $x \bmod a_i = b_i$。样例给出的三条条件是 $x \equiv 1 \pmod 3$、$x \equiv 1 \pmod 5$、$x \equiv 2 \pmod 7$，答案为 $16$。

正解

思路

朴素做法与瓶颈。 最直接的想法是从 $x = 1$ 开始逐个枚举，检查是否每个 $i$ 都满足 $x \bmod a_i = b_i$。枚举的步数是「答案的大小」，而答案可以达到 $\prod a_i$ 量级：约束 $n \leqslant 10$、$a_i \leqslant 1000$ 时 $\prod a_i$ 接近 $10^{30}$，连真实数据里最小的三条件用例（$a = 9982, 9983, 9985$）答案都已是 $206771281471 \approx 2 \times 10^{11}$。所以瓶颈在于：我们在一整个剩余类里逐个试数，而这些数里的有效信息只有「落在哪个剩余类」。

关键观察：同余条件的解集仍是「一个剩余类」。 若干条 $x \equiv b \pmod a$ 同时成立的解，仍然可以写成 $x \equiv v \pmod m$ 的形式，$m$ 是这些模数的乘积。于是可以逐条合并，而不是逐个数枚举。

设已处理的条件合起来等价于 $x \equiv v \pmod m$，即 $x = v + mt$（$t$ 是任意整数）。现在加入新条件 $x \equiv b \pmod a$，代入得

互质性让方程可以一步解出。 题面保证 $a_i$ 两两互质，而 $m$ 是此前若干 $a_j$ 的乘积，所以 $\gcd(m, a) = 1$——$m$ 在模 $a$ 下存在逆元，方程有唯一解类

把 $t$ 归一化到 $[0, a)$ 后取代表元，新的剩余类为

这一步之所以不丢解：$t$ 相差 $a$ 时 $mt$ 相差 $ma = m'$，正是新模数，所以 $t \equiv t_0 \pmod a$ 的全部解给出的是同一个 $x \bmod m'$。

搜索范围的塌缩。 原来的候选是 $10^{30}$ 个 $x$，现在每条条件只需要在 $[0, a)$ 里定一个 $t$，而且 $t$ 不用枚举——乘一次逆元就得到。这正是中国剩余定理的增量（逐条合并）写法。Python 的 pow(m, -1, a) 直接给出模逆元（内部就是扩展欧几里得），把「解同余方程」压成一次调用。

用样例验证推导。 三条条件逐条合并，维护不变量 $x = v + mt$：

观察重点：第 2 步解出 $t = 0$，说明 $3$ 与 $5$ 的公共解里「第一个」就已经满足新条件，于是 $v$ 保持不变而模数涨到 $15$；第 3 步因为 $15 \equiv 1 \pmod 7$，逆元是 $1$，解出 $t = 1$，$v$ 从 $1$ 跳到 $16$。最终 $x \equiv 16 \pmod{105}$，最小正解 $16$，与样例一致。回代校验：

两个容易踩的边界。 其一，$b - v$ 可能是负数（例如 $b = 4$、$v = 5$）：Python 的 % 总返回非负余数，代码里 % a 顺手把它归一化到 $[0, a)$，不需要额外分支，也不会让 $v$ 退化成负数。这一条在 data/input10 里就会遇到——那里的条件从 $(5, 4)$ 起满足 $b_i = a_i - 1$，而合并到该步时 $v = 5$，差值是负数。其二，合并不变量代表的是最小非负解，当所有条件都在 $x = 0$ 同时成立时 $v = 0$，而题目要求正整数，所以代码写 return v or m：$m = \prod a_i$ 同样满足全部条件，且是此时最小的正解（例如 $x \equiv 2 \pmod 2$ 一条，应输出 $2$ 而不是 $0$）。

代码

Python 版：

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 23:20
# update_at: 2026-09-30 23:20

import sys


def merge(v: int, m: int, a: int, b: int) -> tuple[int, int]:
    """并入条件 x ≡ b (mod a)，返回合并后的 (余数, 模数)。

    已解部分等价于 x = v + m*t；代入得 m*t ≡ b - v (mod a)。题面保证 a 两两互质，
    而 m 是此前若干 a 的乘积，故 gcd(m, a) = 1，逆元存在，t 在模 a 下唯一。
    """
    t = (b - v) * pow(m, -1, a) % a  # `% a` 把负差值也归一化到 [0, a)，新余数最小非负
    return v + m * t, m * a          # 新模数 m*a 就是这组条件的公共周期


def crt(congs: list[tuple[int, int]]) -> int:
    """按输入顺序合并同余条件 x ≡ b_i (mod a_i)，返回最小正解。"""
    v, m = 0, 1  # x = 0 + 1*t 对一切 x 成立，是合并的单位元
    for a, b in congs:
        v, m = merge(v, m, a, b)
    return v or m  # v = 0 表示解是周期的整数倍，最少养猪数取 m 本身


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    congs = [(next(data), next(data)) for _ in range(n)]  # 每行一组 (猪圈数, 剩余猪数)
    print(crt(congs))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 23:31
 * update_at: 2026-10-05 23:31
 */

// 曹冲养猪：解两两互质模数下的同余方程组 x ≡ b_i (mod a_i)，输出最小正解。
// 做法：逐条合并剩余类（增量 CRT）。维护不变量 x = v + m*t，
// 新条件代入得 m*t ≡ b - v (mod a)，由互质性用扩展欧几里得求逆元解出 t。

#include <cstdio>

typedef long long ll;
typedef __int128 lll; // 合并模数 m = ∏a_i 最大可达 1000^10 ≈ 10^30，超出 long long，用 __int128

const int MAXN = 15;

int n;
ll a[MAXN]; // a[i]：第 i 次建猪圈的个数（模数）
ll b[MAXN]; // b[i]：第 i 次剩下没去处的猪数（余数）
lll v, m;   // 已合并条件等价于 x = v + m*t，v 是当前最小非负代表元

// 扩展欧几里得：求 a*x + b*y = gcd(a,b) 的一组解，返回 gcd(a,b)
lll exgcd(lll a, lll b, lll &x, lll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    lll x1, y1;
    lll g = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// 并入一条新条件 x ≡ b_ (mod a_)：把 x = v + m*t 代入得 m*t ≡ b - v (mod a)
void merge_cong(ll a_, ll b_) {
    lll a = a_, b = b_;
    lll r = ((b - v) % a + a) % a; // b - v 可能为负，归一化到 [0, a)
    lll x, y;
    exgcd(m % a, a, x, y);     // a 两两互质 ⇒ gcd(m, a) = 1，逆元必存在
    lll inv = (x % a + a) % a; // m 在模 a 下的逆元
    lll t = r * inv % a;       // t ≡ (b - v) * m^{-1} (mod a)，在 [0, a) 内唯一
    v = v + m * t;             // 新的合并余数
    m = m * a;                 // 新的合并模数：这组条件的公共周期
}

// 输出 __int128
void print_lll(lll x) {
    if (x >= 10) print_lll(x / 10);
    int d = (int)(x % 10); // 每次取出的数字在 0..9，降到 int 输出
    putchar('0' + d);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld %lld", &a[i], &b[i]);
    v = 0;
    m = 1; // 无约束：x = 0 + 1*t 对一切 x 成立，是合并的单位元
    for (int i = 1; i <= n; i++) merge_cong(a[i], b[i]);
    if (v == 0) v = m; // 所有条件在 x=0 同时成立时取周期本身，保证输出正整数
    print_lll(v);
    putchar('\n');
    return 0;
}

代码分为三层，与上面的推导一一对应：

• merge(v, m, a, b) 负责单条合并：t = (b - v) * pow(m, -1, a) % a 就是 $t \equiv (b-v)m^{-1} \pmod a$；返回值 v + m * t, m * a 就是 $(v', m')$。pow 的第三个参数为 $-1$ 表示求模逆元，这里依赖 $\gcd(m, a) = 1$。
• crt(congs) 维护不变量 $(v, m)$，初值 v, m = 0, 1 对应「无约束」（$x \equiv 0 \pmod 1$ 对一切 $x$ 成立）；循环结束后 return v or m 处理「解为周期整数倍」时应当输出 $m$ 而不是 $0$。
• solve() 只做读入与输出，(next(data), next(data)) 按题面每行的顺序取 $(a_i, b_i)$。

复杂度

• 时间复杂度：合并 $n$ 次，每次一次扩展欧几里得求逆元，代价 $O(\log a_{\max})$；其余是次数很少的大整数乘除，位数 $B = \sum \log_2 a_i \leqslant 10 \log_2 1000 \approx 100$，每次 $O(B)$。总体

  $$O\!\left(n \left(\log a_{\max} + B\right)\right) \approx O\!\left(n \log \textstyle\prod a_i\right),$$

  在约束下是「$10$ 次 exgcd 加少量百位大数运算」的量级。

• 空间复杂度：只保存 $v$、$m$ 和 $n$ 组输入，$O(n + B)$。

• 对比朴素枚举的 $O(\text{ans} \cdot n)$（$\text{ans}$ 可达 $10^{30}$），这是本质上的降级；求逆元没有用「枚举 $t$ 试 $a$ 次」写，所以整体仍是 $O(n \log)$ 而不是 $O(na)$。

总结

• 「$a_i$ 个一圈剩下 $b_i$ 头」就是同余式 $x \equiv b_i \pmod{a_i}$，题目要求同余方程组的最小正解。
• 逐条合并的核心是维护不变量 $x \equiv v \pmod m$：把旧解写成 $v + mt$ 代入新条件，用 $t \equiv (b-v)m^{-1} \pmod a$ 更新 $(v, m) \to (v + mt,\ ma)$。
• $a_i$ 两两互质 ⇒ $\gcd(m, a) = 1$ ⇒ 逆元存在，合并永远有解，不需要处理一般 CRT 的无解分支。
• 两个实现细节：% a 处理负差值（Python 自动归一化），v or m 处理「输出必须为正」。