【模板】中国剩余定理（CRT）/ 曹冲养猪

• 时间限制：1 秒
• 内存限制：512 MiB

题目描述

曹操想知道养猪场中母猪的数量，曹冲却只给出了一组余数信息。

例如，若共有 $16$ 头母猪，那么把它们分入 $3$ 个猪圈会剩下 $1$ 头，分入 $5$ 个猪圈仍会剩下 $1$ 头，分入 $7$ 个猪圈会剩下 $2$ 头。

现在给定 $n$ 组这样的信息。第 $i$ 组信息表示母猪数量除以 $a_i$ 的余数为 $b_i$。保证 $a_1,a_2,\ldots,a_n$ 两两互质。请求出满足全部条件的最小非负整数。

输入格式

第一行输入一个整数 $n$，表示同余条件的数量。

接下来 $n$ 行，每行输入两个整数 $a_i,b_i$，表示答案满足

$$x\equiv b_i\pmod {a_i}。$$

输出格式

输出一个非负整数，表示满足全部同余条件的最小解。

样例输入 1

3
3 1
5 1
7 2

样例输出 1

16

数据范围

对于所有测试数据：

$$1\le n\le 10,\qquad 0\le b_i<a_i\le 100000,\qquad 1\le\prod_{i=1}^{n}a_i\le 10^{18}，$$

且 $a_1,a_2,\ldots,a_n$ 两两互质。

本题各测试点独立计分。

子任务编号	分值	特殊限制
1	24	$\prod a_i\le 10^6$
2	36	所有 $a_i$ 均为质数
3	40	无特殊限制