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

题目描述

给定 $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$ 。

输出一行一个整数，表示方程组的最小非负整数解。

对于全部数据， $1\le n\le 10^5$ ， $1\le a_i\le 10^{12}$ ， $0\le b_i\le 10^{12}$ ，所有 $a_i$ 的最小公倍数不超过 $10^{18}$ ，且方程组有解。

请注意，中间乘法结果可能超出 64 位有符号整数的范围。