中文
日本語
English
| P2349[模板]扩展中国剩余定理 | ||
|
问题描述
给定$n$个非负整数$a_i,b_i$，求解关于$x$的方程组的最小非负整数解。
\[
\begin{cases}
x\equiv b_1\ (\texttt{mod } a_1)\\
x\equiv b_2\ (\texttt{mod } a_2)\\
...\\
x\equiv b_n\ (\texttt{mod } a_n)\\
\end{cases}
\]
输入格式
输入第一行包含整数$n$。
接下来$n$行，每行两个非负整数$a_i,b_i$。
输出格式
输出一行，为满足条件的最小非负整数$x$。
样例输入
3
11 6
25 9
33 17
样例输出
809
提示
\(n\leq 10^5\)
$1\leq a_i\leq 10^{12}$
$0\leq b_i<a_i$
保证有解，且答案不超过$10^{18}$。注意程序运行过程中运算小心溢出哟！