形式化题目

给定 $n$ 条条件，每条是「$a_i$ 头牛一圈时，最后一圈多出 $b_i$ 头」，即

其中 $a_i$ 两两互质。求满足全部条件的最小正整数 $x$。

题面没有保证 $b_i < a_i$（真实数据里出现 $b_i = 0$ 以及 $b_i = a_i - 1$）， 所以 $b_i$ 应当读作「$x \bmod a_i$ 的一个代表元」，而不是已经归好位的余数； 真实的 $a_i$ 也允许取 $1$。 由于模数两两互质，解在模 $M = \prod_{i=1}^{n} a_i$ 下唯一， $M$ 的上界是 $1.2^{10}\times 10^{60} \approx 6.2\times10^{60}$（约 202 个二进制位）。

样例的三条条件为 $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$，第一个通过的即答案。做法本身正确，但枚举步数就是答案的大小， 而答案落在 $[1, M]$ 之内，$M$ 可以达到 $6.2\times 10^{60}$。真实数据也能看出量级：

光是 input3 就要循环两千亿次。更要紧的是，枚举出来的候选几乎全是废信息： $M$ 个数里只有一个符合全部条件，其余的都只是在重复确认「不在那个剩余类里」。

问题的本质在于，候选虽然有 $6\times10^{60}$ 个，但它们携带的信息只有 $\log_2 M \approx 202$ 比特——也就是「$x$ 落在模 $M$ 的哪一个剩余类里」。 所以应该直接算出那个剩余类，而不是逐个验证。

关键观察：若干条同余式的解集仍然是一个剩余类。 换句话说， 「同时满足 $x\equiv b_1 \pmod{a_1}$ 与 $x \equiv b_2 \pmod{a_2}$」 可以写成「$x \equiv v \pmod m$」的形式，$m = a_1a_2$。 于是可以逐条合并：维护一个不变量 $(v, m)$，表示「到目前为止的所有条件 $\iff x \equiv v \pmod m$」，每读入一条新条件就把这个剩余类与它求交。

怎么合并：把不变量展开代入。 设已合并的部分等价于 $x \equiv v \pmod m$， 也就是 $x = v + mt$（$t$ 为任意整数，代表 $m$ 的各个倍数）。现在加入 $x \equiv b \pmod a$：

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

取 $t_0 \in [0, a)$ 作代表元，新剩余类就是

这样取代表元不丢解。 $mt \equiv b-v \pmod a$ 的全部解是 $t \equiv t_0 \pmod a$ 一整类。 若 $t = t_0 + ka$，则 $x = v + m(t_0 + ka) = v' + k\,ma = v' + k\,m'$， 仍然落在同一个 $x \bmod m'$ 里。所以「在 $[0,a)$ 里挑一个」只是挑代表，不改变解集。

为什么求逆元这一步能直接调用库函数。 解 $mt \equiv b - v \pmod a$ 本来要做一次扩展欧几里得， Python 的 pow(m, -1, a) 就是它的封装，直接把 $m^{-1} \bmod a$ 算出来。 整条合并因此可以写成一行：t = (b - v) * pow(m, -1, a) % a。 这里的 % a 还顺手解决了一个边界：$b - v$ 可能是负数。真实数据 input10 就是这种情形—— 条件从 $(2,1),(3,2),(5,4),\dots,(29,28)$ 依次满足 $b_i = a_i - 1$， 而合并到 $(5,4)$ 时已有 $v = 5$，差值 $b - v = -1$。 C++ 的 % 会得出负数、把 $t$ 带到 $[0,a)$ 之外，必须手写 ((..)%a+a)%a； Python 的 % 总是返回非负余数，所以代码里不需要额外分支。

样例逐步核对。 三条条件 $x \equiv 1 \pmod 3$、$x \equiv 1 \pmod 5$、$x \equiv 2 \pmod 7$， 初值 $v, m = 0, 1$，每步解出 $t$ 后更新：

读表时注意第 2 步：解出 $t = 0$，所以 $v$ 保持 $1$ 不变，而模数从 $3$ 涨到 $15$—— 这一步只是把周期变长，没有挪动解的位置。第 3 步因为 $15 \equiv 1 \pmod 7$ 逆元是 $1$， $t = 1$，$v$ 从 $1$ 跳到 $16$，最终 $x \equiv 16 \pmod{105}$。回代可知 $16 \bmod 3 = 1$、$16 \bmod 5 = 1$、$16 \bmod 7 = 2$ 全部相符。

三个容易踩的边界。 其一，合并出来的是最小非负解，若所有条件在 $x = 0$ 处同时成立 （例如只有一条 $x \equiv 0 \pmod 2$），$v$ 会是 $0$，而题目要的是正整数： 此时 $m$ 本身也满足全部条件，且是最小的正解，所以代码写 print(v or m)。 其二，$b - v$ 可能是负数（input10 的每条都满足 $b_i = a_i - 1$，合并到 $(5,4)$ 时 $v = 5$）： Python 的 % 直接返回 $[0,a)$ 内的余数，不需要像 C++ 那样手写 ((..)%a+a)%a。 其三，$a_i = 1$ 是允许的（真实数据 input9 第一条就是 1 0）： pow(m, -1, 1) 定义为 $0$，于是 $t = 0$、状态不变，正好等价于「这条条件什么也没约束」； 所以读入时不要假设 $1 \leqslant b_i < a_i$。

代码

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#!/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-10-01 17:03
# update_at: 2026-10-01 17:10

import sys


def merge(v: int, m: int, a: int, b: int) -> tuple[int, int]:
    """并入条件 x ≡ b (mod a)：由 x = v + m*t 解出 t，返回新剩余类的 (余数, 模数)。"""
    t = (b - v) * pow(m, -1, a) % a  # 解 m*t ≡ b-v (mod a)；a_i 两两互质，故 m 可逆
    return (v + m * t) % (m * a), m * a


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)

    v, m = 0, 1  # 空约束：x ≡ 0 (mod 1) 对一切 x 成立，是合并的单位元
    for _ in range(n):
        a, b = next(data), next(data)  # 建 a 个棚剩 b 头牛，即 x ≡ b (mod a)
        v, m = merge(v, m, a, b)

    print(v or m)  # v 是 [0, m) 内的解，题目要正整数：v = 0 时取周期 m


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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140/**
 * 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-06 18:43
 * update_at: 2026-10-06 18:43
 */

#include <cstdio>

typedef long long ll;

// 模数 a_i 两两互质，最终模数 M 最大约 6.2e60（61 位十进制），
// 超过 64 位范围，所以自己写一个 1e9 进制的简单大整数。
const int MAXL = 12;         // 12 个 1e9 进制位可存 108 位十进制，足够放下 M
const ll BASE = 1000000000LL;

struct Big {
    int len;                 // 有效位数
    ll d[MAXL];              // 低位在前，每位的基是 BASE
};

Big g_v;                     // 当前不变量 x ≡ g_v (mod g_m) 的余数
Big g_m;                     // 当前不变量的模数

// 大整数乘小数 k：把 x 就地乘上 k
void mul_small(Big &x, ll k) {
    ll carry = 0;
    for (int i = 0; i < x.len; i++) {
        ll cur = x.d[i] * k + carry;
        x.d[i] = cur % BASE;
        carry = cur / BASE;
    }
    while (carry > 0 && x.len < MAXL) {
        x.d[x.len] = carry % BASE;
        carry /= BASE;
        x.len++;
    }
    while (x.len > 1 && x.d[x.len - 1] == 0) x.len--;   // 去掉高位 0，保证表示唯一
}

// 大整数加法：x += y
void add_big(Big &x, const Big &y) {
    ll carry = 0;
    int n = x.len > y.len ? x.len : y.len;
    for (int i = 0; i < n; i++) {
        ll cur = carry;
        if (i < x.len) cur += x.d[i];
        if (i < y.len) cur += y.d[i];
        x.d[i] = cur % BASE;
        carry = cur / BASE;
    }
    x.len = n;
    if (carry > 0 && x.len < MAXL) {
        x.d[x.len] = carry;
        x.len++;
    }
    while (x.len > 1 && x.d[x.len - 1] == 0) x.len--;   // 去掉高位 0，保证表示唯一
}

// 大整数对小数 a 取模，返回 [0, a) 内的余数
ll mod_small(const Big &x, ll a) {
    if (a == 1) return 0;
    ll rem = 0;
    for (int i = x.len - 1; i >= 0; i--) {
        rem = (rem * BASE + x.d[i]) % a;
    }
    return rem;
}

// 扩展欧几里得：求 gcd(a, b) 以及一组解 a*x + b*y = gcd
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll g = exgcd(b, a % b, x, y);
    ll nx = y;
    ll ny = x - (a / b) * y;
    x = nx;
    y = ny;
    return g;
}

// 求 a 在模 mod 下的逆元；mod = 1 时约定逆元为 0
ll mod_inverse(ll a, ll mod) {
    if (mod == 1) return 0;
    ll x, y;
    exgcd(a, mod, x, y);
    return (x % mod + mod) % mod;
}

// 输出大整数（不带前导零）
void print_big(const Big &x) {
    printf("%lld", x.d[x.len - 1]);
    for (int i = x.len - 2; i >= 0; i--) {
        printf("%09lld", x.d[i]);
    }
    printf("\n");
}

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

    // 空约束的单位元：x ≡ 0 (mod 1) 对一切 x 成立
    g_v.len = 1;
    g_v.d[0] = 0;
    g_m.len = 1;
    g_m.d[0] = 1;

    for (int i = 1; i <= n; i++) {
        ll a, b;
        scanf("%lld%lld", &a, &b);

        // 已合并部分等价于 x = g_v + g_m * t，代入 x ≡ b (mod a)
        // 得 g_m * t ≡ b - g_v (mod a)，a_i 两两互质故 g_m 可逆
        ll v_mod_a = mod_small(g_v, a);
        ll m_mod_a = mod_small(g_m, a);
        ll inv = mod_inverse(m_mod_a, a);
        ll diff = ((b - v_mod_a) % a + a) % a;   // 归一化到 [0, a)
        ll t = diff * inv % a;

        // 合并：新模数 m*a，新余数 v + m*t（一定落在 [0, m*a) 内）
        Big mt = g_m;
        mul_small(mt, t);
        add_big(g_v, mt);
        mul_small(g_m, a);
    }

    // g_v 是 [0, g_m) 内的解；题目要求正整数，g_v = 0 时取最小正解 g_m
    if (g_v.len == 1 && g_v.d[0] == 0) {
        print_big(g_m);
    } else {
        print_big(g_v);
    }

    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), m*a 对应 $(v', m')$。 末尾的 % (m*a) 不是必需的（结果本来就在 $[0, ma)$ 内），写出来是为了让 「返回值永远是最小非负代表元」这个约定在函数边界上自明。
• solve() 里的 v, m = 0, 1 是合并的单位元：$x \equiv 0 \pmod 1$ 对一切 $x$ 成立。 循环恰好执行 $n$ 次，每次消费一对 $(a, b)$，循环体内没有任何分支。
• print(v or m) 处理「答案必须是正整数」这一条。

复杂度

• 时间复杂度：合并 $n$ 次，每次一次扩展欧几里得求逆元 $O(\log a_{\max})$， 加上次数很少的大整数运算。设最终模数的位数为 $B = \sum \log_2 a_i \leqslant 202$， 则总时间

  $$O\!\left(\sum_{i=1}^{n}\left(\log a_i + B\right)\right) = O\!\left(n\log a_{\max} + nB\right),$$

  也就是「$10$ 次 exgcd 加少量 200 位大数运算」的量级。实测真实数据最慢一组 $0.018$ s， 手工构造的 $n = 10$、每个模数都在 $1.2\times10^6$ 附近、答案长达 61 位的极限用例 $0.017$ s， 远低于 1000 ms 限时。

• 空间复杂度：只保存当前 $(v, m)$ 与输入缓冲，$O(n + B)$，实测峰值 RSS 14.6 MB。

• 与朴素做法对比：朴素枚举是 $O(\text{ans}\cdot n)$，其中 $\text{ans}$ 可达 $6.2\times10^{60}$； 这里是 $O(n\log M)$。差别不是常数，而是「枚举剩余类里的每个数」被换成了「直接算出这个剩余类」。

总结

• 「建 $a_i$ 个牛棚剩 $b_i$ 头牛」就是同余式 $x \equiv b_i \pmod{a_i}$，题目求同余方程组的最小正解。
• 朴素枚举的瓶颈不是常数，而是在一个剩余类里逐个试数；$M$ 有 $10^{60}$ 量级， 但它只携带 $\log_2 M \approx 202$ 比特信息。
• 逐条合并的核心是维护不变量 $x \equiv v \pmod m$：把旧解写成 $v + mt$ 代入新条件， 用 $t \equiv (b-v)m^{-1} \pmod a$ 更新成 $(v + mt,\ ma)$。
• $a_i$ 两两互质 $\Rightarrow \gcd(m,a) = 1 \Rightarrow$ 逆元总存在， 合并永远有解，不需要写一般 CRT 的无解分支；pow(m, -1, a) 直接给出逆元。
• 三个实现细节：% a 自动把负的 $b - v$ 归一到 $[0,a)$；v or m 保证输出是正整数； $a_i = 1$ 时 pow(m, -1, 1) = 0，状态自动不变，不必特判。

图示解析

先用一张图对比「朴素枚举」与「逐条合并」两条路线，说明优化究竟消除了什么：

flowchart TD
    P["n 条同余式 x ≡ b_i (mod a_i)"] --> B1["朴素：x = 1, 2, 3, ... 逐个检验"]
    B1 --> B2["每个候选都要花 O(n) 验证"]
    B2 --> B3["步数 = 答案本身，可达 10^60 量级 · 超时"]

    P --> C1["关键观察：解集仍是单个剩余类"]
    C1 --> C2["维护不变量 x ≡ v (mod m)，初值 (0, 1)"]
    C2 --> C3["代入 x = v + mt 解出 t ≡ (b-v)·m⁻¹ (mod a)"]
    C3 --> C4["更新 (v, m) ← (v + mt, m·a)，共 n 轮"]
    C4 --> C5["输出 [0, m) 内最小正解：v or m"]

图中上半支是朴素路线：它的每一步只回答「这个数行不行」，信息量为 1 比特， 却要重复 $10^{60}$ 次。下半支是正解路线：第 3 步把「检验」换成「解方程」， 一次就锁定整个剩余类；第 4 步的每一轮都只做常数次大数运算， 所以总代价从「答案的量级」降到「$n$ 轮」。

再看合并过程中「解在数轴上的位置」如何被一步步锁定：

1
2
3
4第 1 条 x ≡ 1 (mod 3)   候选：1, 4, 7, 10, 13, 16, 19, 22, ...   -> v=1,  m=3
第 2 条 x ≡ 1 (mod 5)   取交集：1, 16, 31, 46, 61, ...           -> v=1,  m=15
第 3 条 x ≡ 2 (mod 7)   取交集：16, 121, 226, ...                 -> v=16, m=105
                                  ^^ 第一个正解就是 16

三行的模数依次是 $3 \to 15 \to 105$（每次乘上新模数），而候选序列之间的间隔同步变宽： 条件越多，候选越稀疏，但代表元始终只有一个，所以不需要保留整个序列，只要 $(v, m)$ 两个数。 这正是不变量「$x = v + mt$」的几何含义：$v$ 指出解在哪，$m$ 指出下一次出现在多远之后。