1634：【例 4】曹冲养猪

题目描述

自从曹冲搞定了大象以后，曹操就开始琢磨让儿子干些事业，于是派他到中原养猪场养猪，可是曹冲很不高兴，于是在工作中马马虎虎，有一次曹操想知道母猪的数量，于是曹冲想狠狠耍曹操一把。

举个例子，假如有 $16$ 头母猪，如果建了 $3$ 个猪圈，剩下 $1$ 头猪就没有地方安家了；如果建造了 $5$ 个猪圈，但是仍然有 $1$ 头猪没有地方去；如果建造了 $7$ 个猪圈，还有 $2$ 头没有地方去。你作为曹总的私人秘书理所当然要将准确的猪数报给曹总，你该怎么办？

输入格式

第一行包含一个整数 $n$，表示建立猪圈的次数；

接下来 $n$ 行，每行两个整数 $a_i, b_i$，表示建立了 $a_i$ 个猪圈，有 $b_i$ 头猪没有去处。你可以假定 $a_i, a_j$ 互质。

输出格式

输出仅包含一个正整数，即为曹冲至少养猪的数目。

样例

样例输入 #1

3
3 1
5 1
7 2

样例输出 #1

16

样例解释 #1

• $n=3$ 组条件：
  1. $x \equiv 1 \pmod{3}$
  2. $x \equiv 1 \pmod{5}$
  3. $x \equiv 2 \pmod{7}$
• 求最小的正整数 $x$ 满足以上同余方程组。
• 解为 $x=16$（因为 $16 \bmod 3 = 1$，$16 \bmod 5 = 1$，$16 \bmod 7 = 2$）。

数据范围

对于全部数据：

• $1 \le n \le 10$
• $1 \le b_i \le a_i \le 1000$
• 保证 $a_i$ 两两互质

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题是中国剩余定理（Chinese Remainder Theorem, CRT）的模板题。给定同余方程组：

$$\begin{cases} x \equiv b_1 \pmod{a_1} \\ x \equiv b_2 \pmod{a_2} \\ \cdots \\ x \equiv b_n \pmod{a_n} \end{cases}$$

其中 $a_i$ 两两互质，求最小的正整数解 $x$。

解法：

1. 计算 $M = a_1 \times a_2 \times \cdots \times a_n$。
2. 对于每个 $i$，计算 $M_i = M / a_i$。
3. 计算 $M_i$ 在模 $a_i$ 下的逆元 $t_i$（即 $M_i \cdot t_i \equiv 1 \pmod{a_i}$）。
4. 则解为 $x = \sum_{i=1}^n b_i \cdot M_i \cdot t_i \pmod{M}$。
5. 最小正整数解为 $(x \bmod M + M) \bmod M$，如果结果为 $0$ 则取 $M$（但题目保证有正整数解，且 $b_i \ge 1$，所以 $x$ 应该大于 $0$）。

由于 $a_i$ 较小，且 $n \le 10$，可以直接用扩展欧几里得算法求逆元。注意 $M$ 可能很大（最大 $1000^{10}$ 会溢出），但题目只要求输出最小正整数解，且 $a_i \le 1000$，$n \le 10$，$M$ 可能超过 long long 范围？实际上 $1000^{10} = 10^{30}$，远远超过 long long。但中国剩余定理计算过程中需要用到 $M$ 的乘积，可能溢出。但我们可以使用逐步合并法来避免大数运算。

逐步合并法： 设有两个同余方程：

$$x \equiv b_1 \pmod{a_1}$$ $$x \equiv b_2 \pmod{a_2}$$

其中 $\gcd(a_1,a_2)=1$。则合并后的解为：

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

其中 $k$ 满足 $a_1 \cdot k \equiv b_2 - b_1 \pmod{a_2}$。由于 $\gcd(a_1,a_2)=1$，可以解出 $k$（用扩展欧几里得求 $a_1$ 模 $a_2$ 的逆元，然后 $k = (b_2 - b_1) \cdot a_1^{-1} \bmod a_2$）。然后合并后的模数为 $a_1 a_2$，余数为 $b_1 + a_1 \cdot k$（取模 $a_1 a_2$）。依次合并所有方程，最终得到解。

这样每一步的模数和余数都在 long long 范围内（因为 $a_i \le 1000$，乘积最大 $10^{30}$，但逐步合并时，当前模数 $M$ 不超过已合并的 $a_i$ 乘积，当合并到第 $10$ 个时可能溢出 long long。实际上 $1000^{10}$ 远大于 long long，但题目数据可能保证答案在 long long 范围内？样例答案 $16$ 很小。但为了安全，可以使用高精度或 __int128（如果编译器支持）。由于 $n \le 10$，$a_i \le 1000$，乘积最大 $10^{30}$，可以用 __int128 存储。如果不支持 __int128，则需要用高精度。但本题数据较小，可能答案在 long long 范围内，可以直接用 long long，但要注意乘法溢出，可以使用快速乘或 __int128 辅助。

使用中国剩余定理的标准公式时，如果直接用 long long 计算 $M$ 可能会溢出，所以建议使用逐步合并法，并用 __int128 或高精度。由于 $n$ 很小，可以手动实现高精度（或使用 Python）。但鉴于 C++ 环境可能不支持 __int128，可以用 long double 或拆分计算，但最稳妥的方法是使用高精度类。考虑到题目难度，数据可能保证答案在 long long 范围内，但未明确说明。我们可以使用逐步合并法，每次合并时用扩展欧几里得求解，并用 __int128 临时计算。