問題一覧 > 通常問題

No.187 Chinese Style (Hard)

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 128 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 179
作問者 : LayCurse
お気に入りにしたユーザー ProblemId : 448 / 自分の提出
問題文最終更新日: 2026-06-25 19:49:05
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 98 (順位表) の他の問題:

Problem Statement

In some foreign countries, there seem to be problems with many answers, such as ○＋□＝8, but grading them must be tough, right?
This time, let's try giving it a Chinese-style arrangement.

You are given $N$ $2$-tuples of integers $(X_1, Y_1),(X_2, Y_2), \ldots ,(X_N, Y_N)$. Find a positive integer to fill in □ that simultaneously satisfies
　　□ ${\rm mod}\ Y_k = X_k, \quad k=1,2,\ldots,N$
.
Hmm, this may have many answers.
In that case, find the smallest one.
Even the smallest one may be a large number, so report only the remainder of the answer when divided by $10^9+7$.

Input

$N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_N$ $Y_N$

$1 \leq N \leq 1000$
$0 \leq X_i < Y_i \leq 1000000000 = 10^9$

Output

Output the remainder when the smallest positive integer that fits in □ is divided by $10^9+7$.
However, if no such integer exists, output $\verb|-1|$ instead.

Sample

Sample 1
Input
3
10 20
10 30
10 40
Output
10

The remainder is $10$ whether you divide by $20$, by $30$, or by $40$, so this just has to be $10$.

Sample 2
Input
3
10 20
10 30
30 40
Output
70

The remainder is $10$ whether you divide by $20$ or by $30$, so... oh, it was $70$.

Sample 3
Input
3
1 2
0 4
5 17
Output
-1

It is not divisible by $2$, so how could it be divisible by $4$?

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。