#P4777. 【模板】扩展中国剩余定理(EXCRT)

    ID: 4849 远端评测题 1000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>最大公约数,gcd中国剩余定理,CRT

【模板】扩展中国剩余定理(EXCRT)

题目描述

给定 nn 组非负整数 ai,bia_i, b_i ,求解关于 xx 的方程组的最小非负整数解。

$$\begin{cases} x \equiv b_1\ ({\rm mod}\ a_1) \\ x\equiv b_2\ ({\rm mod}\ a_2) \\ ... \\ x \equiv b_n\ ({\rm mod}\ a_n)\end{cases} $$

输入格式

输入第一行包含整数 nn

接下来 nn 行,每行两个非负整数 ai,bia_i, b_i

输出格式

输出一行,为满足条件的最小非负整数 xx

3
11 6
25 9
33 17

809

提示

对于 100%100 \% 的数据,1n1051 \le n \le {10}^51bi,ai10121 \le b_i,a_i \le {10}^{12},保证所有 aia_i 的最小公倍数不超过 1018{10}^{18}

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

数据保证有解。