V. 【模板】扩展中国剩余定理（EXCRT）

远端评测题

1000ms

500MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定 $n$ 组非负整数 $a_i, b_i$ ，求解关于 $x$ 的方程组的最小非负整数解。

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

输入第一行包含整数 $n$ 。

接下来 $n$ 行，每行两个非负整数 $a_i, b_i$ 。

输出一行，为满足条件的最小非负整数 $x$ 。

对于 $100 \%$ 的数据， $1 \le n \le {10}^5$ ， $1 \le b_i,a_i \le {10}^{12}$ ，保证所有 $a_i$ 的最小公倍数不超过 ${10}^{18}$ 。

请注意程序运行过程中进行乘法运算时结果可能有溢出的风险。

数据保证有解。