1635：【例 5】Strange Way to Express Integers

题目描述

给定 $2n$ 个正整数 $a_1, a_2, \cdots, a_n$ 和 $m_1, m_2, \cdots, m_n$，求一个最小的正整数 $x$，满足 $\forall i \in [1,n], x \equiv a_i \pmod{m_i}$，或者给出无解。

输入格式

多组数据。

每组数据第一行一个整数 $n$；

接下来 $n$ 行，每行两个整数 $m_i, a_i$。

输出格式

对于每组数据，若无解，输出 $-1$；否则输出一个非负整数，若有多解，输出最小的满足条件的答案。

样例

样例输入 #1

2
8 7
11 9

样例输出 #1

31

样例解释 #1

• $n=2$，两个方程：
  1. $x \equiv 7 \pmod{8}$
  2. $x \equiv 9 \pmod{11}$
• 最小的正整数解 $x=31$（因为 $31 \bmod 8 = 7$，$31 \bmod 11 = 9$）。

数据范围

对于全部数据：

• 所有的输入都是非负的，并且可以用 $64$ 位有符号整数表示。
• 保证 $1 \le n \le 10^5$，$m_i > a_i$。

时空限制

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

注意：本题是扩展中国剩余定理（ExCRT）的模板题。与普通中国剩余定理不同，这里的模数 $m_i$ 不一定两两互质。因此需要使用扩展中国剩余定理求解同余方程组。

扩展中国剩余定理的核心思想是逐步合并同余方程。考虑两个方程：

$$\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \end{cases}$$

这等价于存在整数 $k_1, k_2$ 使得：

$$x = a_1 + m_1 k_1 = a_2 + m_2 k_2$$

移项得：

$$m_1 k_1 - m_2 k_2 = a_2 - a_1$$

这是一个线性丢番图方程。设 $d = \gcd(m_1, m_2)$，方程有解当且仅当 $d \mid (a_2 - a_1)$。如果无解，则整个方程组无解。

如果有解，可以用扩展欧几里得算法求出 $k_1$ 的一个特解 $k_1'$，则通解为：

$$k_1 = k_1' + \frac{m_2}{d} t$$

其中 $t$ 是任意整数。代入 $x = a_1 + m_1 k_1$ 得：

$$x = a_1 + m_1 \left( k_1' + \frac{m_2}{d} t \right) = (a_1 + m_1 k_1') + \frac{m_1 m_2}{d} t$$

这表示 $x$ 可以写成 $x \equiv x_0 \pmod{M}$ 的形式，其中 $x_0 = a_1 + m_1 k_1'$，$M = \mathrm{lcm}(m_1, m_2) = \frac{m_1 m_2}{d}$。

因此，我们将两个方程合并为一个新的方程 $x \equiv x_0 \pmod{M}$。重复这个过程，直到合并所有方程，最后得到 $x \equiv x_0 \pmod{M}$，最小正整数解为 $x_0 \bmod M$（如果 $x_0$ 为负数，调整到 $[0, M-1]$）。

算法步骤（对于每组数据）：

1. 初始化 $x_0 = 0$, $M = 1$（表示当前解为 $x \equiv 0 \pmod{1}$，即任意整数）。
2. 依次读入每个 $(m_i, a_i)$，设当前方程为 $x \equiv a_i \pmod{m_i}$。
3. 合并方程 $x \equiv x_0 \pmod{M}$ 和 $x \equiv a_i \pmod{m_i}$：
   • 计算 $d = \gcd(M, m_i)$。
   • 如果 $(a_i - x_0)$ 不能被 $d$ 整除，则无解，输出 $-1$。
   • 否则，用扩展欧几里得算法求 $p, q$ 使得 $p M + q m_i = d$。
   • 计算 $k = (a_i - x_0) / d$。
   • 计算新的 $x_0 = x_0 + M \cdot p \cdot k$（注意可能溢出，需要取模新模数）。
   • 计算新的 $M = \mathrm{lcm}(M, m_i) = M / d * m_i$。
   • 调整 $x_0$ 为正且小于 $M$：$x_0 = (x_0 \bmod M + M) \bmod M$。
4. 合并完所有方程后，输出 $x_0$（即最小非负整数解）。

注意：由于 $m_i, a_i$ 可以用 $64$ 位有符号整数表示，计算过程中可能溢出，需要使用 __int128 或快速乘来避免溢出。例如，计算 $M \cdot p \cdot k$ 可能超过 long long 范围，可以先用 __int128 计算再取模，或者使用快速乘（龟速乘）在取模意义下计算。

由于 $n \le 10^5$，需要高效实现，但扩展欧几里得算法是 $O(\log \min(M, m_i))$，总复杂度 $O(n \log M)$，可以接受。

注意多组数据，直到 EOF。