3479. [POJ 2891]表达整数的奇怪方式

【题目描述】

给定$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(\mathrm{mod}\;m_i)$，或者给出无解。

【输入格式】

第一行包含整数$n$。

第2到$n+1$行：每行两个用空格隔开正整数$a_i$和$m_i$。

【输出格式】

输出最小负整数$x$，如果$x$不存在，则输出$-1$。

如果存在$x$，则保证$x$一定在64位整数范围内。

【样例输入】

2
8 7
11 9

【样例输出】

31

【数据范围】

$1\leq a_i\leq 2^{31}-1$

$0\leq m_i<a_i$

$1\leq n\leq 25$

【来源】

《算法竞赛进阶指南》