阿九的奶牛

题目描述

自从朱最学搞定了 QQ 农场以后，就开始捉摸去 QQ 牧场干些事业，不仅在自己的牧场养牛，还到阿九的牧场放牛！

阿九很生气，有一次朱最学想知道阿九牧场奶牛的数量，于是阿九想狠狠耍朱最学一把。

问题描述

举个例子，假如有 16 头奶牛：

• 如果建了 3 个牛棚，剩下 1 头牛就没有地方安家了
• 如果建造了 5 个牛棚，但是仍然有 1 头牛没有地方去
• 如果建造了 7 个牛棚，还有 2 头没有地方去

你作为阿九的私人秘书理所当然要将准确的奶牛数报给阿九，你该怎么办？

输入格式

第一行包含一个整数 $n$ 表示建立牛棚的次数。

接下来 $n$ 行，每行两个整数 $a_i, b_i$，表示建立了 $a_i$ 个牛棚，有 $b_i$ 头牛没有去处。

你可以假定不同 $a_i$ 之间互质。

输出格式

输出包含一个正整数，即为阿九至少养奶牛的数目。

数据范围

• $1 \le n \le 10$
• $1 \le a_i, b_i \le 1200000$
• 所有 $a_i$ 的乘积不超过 $10^{12}$

输入样例

3
3 1
5 1
7 2

输出样例

16

样例解释

输入表示：

1. 建3个牛棚，剩1头牛：$N \equiv 1 \pmod{3}$
2. 建5个牛棚，剩1头牛：$N \equiv 1 \pmod{5}$
3. 建7个牛棚，剩2头牛：$N \equiv 2 \pmod{7}$

求最小的正整数 $N$ 满足以上三个同余方程。

验证 $N=16$：

• $16 \div 3 = 5 \cdots 1$ ✓
• $16 \div 5 = 3 \cdots 1$ ✓
• $16 \div 7 = 2 \cdots 2$ ✓

所以阿九至少有16头奶牛。

问题建模

这是一个中国剩余定理（Chinese Remainder Theorem，CRT）问题。

我们有 $n$ 个同余方程：

$$\begin{cases} N \equiv b_1 \pmod{a_1} \\ N \equiv b_2 \pmod{a_2} \\ \vdots \\ N \equiv b_n \pmod{a_n} \end{cases}$$

其中 $a_1, a_2, \ldots, a_n$ 两两互质。

中国剩余定理

设 $M = a_1 \times a_2 \times \cdots \times a_n$，$M_i = M / a_i$。

由于 $a_i$ 两两互质，所以 $M_i$ 与 $a_i$ 互质，存在整数 $t_i$ 使得：

$$M_i \cdot t_i \equiv 1 \pmod{a_i}$$

即 $t_i$ 是 $M_i$ 模 $a_i$ 的逆元。

那么方程组的解为：

$$N \equiv \sum_{i=1}^n b_i \cdot M_i \cdot t_i \pmod{M}$$

最小正整数解为：

$$N = \left( \sum_{i=1}^n b_i \cdot M_i \cdot t_i \right) \mod M$$

算法步骤

方法1：扩展欧几里得算法

对于每个 $i$：

1. 计算 $M_i = M / a_i$
2. 使用扩展欧几里得算法求 $M_i$ 模 $a_i$ 的逆元 $t_i$，即解方程：$$M_i \cdot t_i + a_i \cdot k = 1$$
3. 计算 $c_i = b_i \cdot M_i \cdot t_i$
4. 最终 $N = \left( \sum_{i=1}^n c_i \right) \mod M$

方法2：逐步合并法（更稳定）

也可以每次合并两个方程：

$$\begin{cases} N \equiv b_1 \pmod{a_1} \\ N \equiv b_2 \pmod{a_2} \end{cases}$$

设 $N = a_1 \cdot x + b_1$，代入第二个方程：

$$a_1 \cdot x + b_1 \equiv b_2 \pmod{a_2}$$ $$a_1 \cdot x \equiv b_2 - b_1 \pmod{a_2}$$

设 $d = \gcd(a_1, a_2)$，由于 $a_1, a_2$ 互质，$d=1$，所以方程有解。

解出 $x \equiv x_0 \pmod{a_2}$，则：

$$N \equiv a_1 \cdot x_0 + b_1 \pmod{a_1 \cdot a_2}$$

这样就将两个方程合并为一个。重复这个过程直到所有方程合并。

示例计算（输入样例）

方法1：直接应用CRT

方程：

1. $N \equiv 1 \pmod{3}$
2. $N \equiv 1 \pmod{5}$
3. $N \equiv 2 \pmod{7}$

步骤1：计算 $M$ $M = 3 \times 5 \times 7 = 105$

步骤2：计算 $M_i$ 和 $t_i$

1. $M_1 = 105/3 = 35$，求 $35 \cdot t_1 \equiv 1 \pmod{3}$

   • $35 \mod 3 = 2$，所以 $2 \cdot t_1 \equiv 1 \pmod{3}$
   • $t_1 = 2$（因为 $2 \times 2 = 4 \equiv 1 \pmod{3}$）
   • $c_1 = b_1 \cdot M_1 \cdot t_1 = 1 \times 35 \times 2 = 70$

2. $M_2 = 105/5 = 21$，求 $21 \cdot t_2 \equiv 1 \pmod{5}$

   • $21 \mod 5 = 1$，所以 $1 \cdot t_2 \equiv 1 \pmod{5}$
   • $t_2 = 1$
   • $c_2 = 1 \times 21 \times 1 = 21$

3. $M_3 = 105/7 = 15$，求 $15 \cdot t_3 \equiv 1 \pmod{7}$

   • $15 \mod 7 = 1$，所以 $1 \cdot t_3 \equiv 1 \pmod{7}$
   • $t_3 = 1$
   • $c_3 = 2 \times 15 \times 1 = 30$

步骤3：计算 $N$ $N = (70 + 21 + 30) \mod 105 = 121 \mod 105 = 16$

得到 $N = 16$。

方法2：逐步合并

合并第1、2个方程： $N \equiv 1 \pmod{3}$ 且 $N \equiv 1 \pmod{5}$

设 $N = 3x + 1$，代入第二个方程： $3x + 1 \equiv 1 \pmod{5}$ ⇒ $3x \equiv 0 \pmod{5}$

由于 $3$ 和 $5$ 互质，$3$ 在模5下有逆元（$3 \times 2 = 6 \equiv 1 \pmod{5}$），两边乘2： $x \equiv 0 \pmod{5}$

所以 $x = 5k$，$N = 3 \cdot 5k + 1 = 15k + 1$

合并后：$N \equiv 1 \pmod{15}$

合并第3个方程： $N \equiv 1 \pmod{15}$ 且 $N \equiv 2 \pmod{7}$

设 $N = 15y + 1$，代入：$15y + 1 \equiv 2 \pmod{7}$ ⇒ $15y \equiv 1 \pmod{7}$

$15 \mod 7 = 1$，所以 $y \equiv 1 \pmod{7}$

$y = 7t + 1$，$N = 15(7t+1) + 1 = 105t + 16$

最小正整数解：$N = 16$

数据范围分析

• $n \le 10$，$a_i \le 1.2 \times 10^6$
• 所有 $a_i$ 的乘积不超过 $10^{12}$
• 结果 $N$ 可能接近 $10^{12}$，需要使用 long long 类型

扩展欧几里得算法

求 $ax + by = \gcd(a,b)$ 的解：

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

求逆元：解 $a \cdot x \equiv 1 \pmod{m}$，即 $ax + my = 1$。

注意事项

1. 模数互质：题目保证 $a_i$ 两两互质，这是CRT可解的条件
2. 数据范围：乘积可能达到 $10^{12}$，中间计算可能溢出，需要使用 long long 并注意乘法溢出
3. 最小正整数解：CRT给出的是模 $M$ 意义下的解，最小正整数解为 $(N \mod M + M) \mod M$，但注意如果结果为0，则解为 $M$
4. 验证：可以验证解是否满足所有方程

时间复杂度

• 扩展欧几里得：$O(\log \min(a,b))$
• 总体：$O(n \log M)$，可以接受

时空限制

• 时间限制：1秒
• 空间限制：64MB