Toggle navigation
NKZX_NOI_OJ
常见问答
题库
来源/分类
状态
排名
竞赛&作业
Login
问题1551--Strange Way to Express Integers
1551: Strange Way to Express Integers
时间限制:
1 Sec
内存限制:
128 MB
提交:
14
解决:
1
[
提交
] [
状态
] [
讨论版
] [命题人:
]
题目描述
给定 2n 个正整数 a
1
,a
2
,⋯,a
n
和 m
1
,m
2
,⋯,m
n
，求一个最小的正整数 x，满足 ∀i∈[1,n],x≡a
i
(mod m
i
)，或者给出无解。
输入
多组数据。
每组数据第一行一个整数 n；
接下来 n 行，每行两个整数 m
i
,a
i
。
输出
对于每组数据，若无解，输出 −1；否则输出一个非负整数，若有多解，输出最小的满足条件的答案。
样例输入
Copy
2 8 7 11 9
样例输出
Copy
31
提示
数据范围与提示：
对于全部数据，所有的输入都是非负的，并且可以用 64 位有符号整数表示。保证 1≤n≤10
5
,m
i
>a
i
。
来源/分类
数学基础
同余问题