題目 2531:
信息學(xué)奧賽一本通T1635-Strange Way to Express Integers
時間限制: 2s
內(nèi)存限制: 192MB 提交: 10 解決: 3
題目描述
原題來自：POJ 2891
給定 2n 個正整數(shù) a1,a2,?,an和 m1,m2,?,mn ，求一個最小的正整數(shù) x，滿足 ?i∈[1,n],x≡ai (mod mi)，或者給出無解。
輸入格式
多組數(shù)據(jù)。
每組數(shù)據(jù)第一行一個整數(shù) n；
接下來 n 行，每行兩個整數(shù) mi,ai 。
輸出格式
對于每組數(shù)據(jù)，若無解，輸出 ?1；否則輸出一個非負(fù)整數(shù)，若有多解，輸出最小的滿足條件的答案。
提示
數(shù)據(jù)范圍與提示：
對于全部數(shù)據(jù)，所有的輸入都是非負(fù)的，并且可以用 64 位有符號整數(shù)表示。保證 1≤n≤105,mi>ai 。