問題一覧 > 通常問題

No.1544 [Cherry 2nd Tune C] Synchroscope

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 103
作問者 : KazunKazun / テスター : Manuel1024Manuel1024
1 ProblemId : 6148 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-06-01 23:13:57

問題文

2つの数列 $X,Y$ がある. 数列 $X$ は長さが $N$ の 数列 $A$ を無限に繰り返しており, 数列 $Y$ は長さ $M$ の数列 $B$ を無限に繰り返す.

より厳密には, 数列 $X$ は数列 $A$ を用いて, $X=(A_1,A_2,\dots, A_N,A_1,\dots,A_N,A_1,\dots,A_N,\dots)$ のように構成されている. $Y$ についても同様である.

このとき, $X_i=Y_i$ を満たす正の整数 $i$ が存在すれば, そのような整数のうち, 最小のものを出力せよ. もし, 存在しなければ, その旨を報告せよ.

なお, 数列の初項は第 $1$ 項とする. また, 数列 $Z$ と正の整数 $r$ に対して, $Z_r$ で数列 $Z$ の第 $r$ 項を表すとする.

制約

  • $1 \leq N,M \leq 5000$
  • $1 \leq A_i,B_i \leq 10^4$
  • 入力は全て整数である.

入力

入力は以下の形式で標準入力から与えられる.

$N$ $M$
$A_1$ $\dots$ $A_N$
$B_1$ $\dots$ $B_M$

出力

$X_i=Y_i$ を満たす正の整数 $i$ が存在すれば, そのような整数のうち最小のものを, 存在しなければ, $-1$ を出力せよ. 最後に改行を忘れないこと.

サンプル

サンプル1
入力
2 3
1 2
2 3 3
出力
4

$A=(1,2), B=(2,3,3)$ より, $X=(1,2,1,2,1,2,\dots), Y=(2,3,3,2,3,3,2,3,3,\dots)$ である. このとき, $X_1 \neq Y_1, X_2 \neq Y_2, X_3 \neq Y_3, X_4=Y_4$ であることから, 答えは $4$ である.

サンプル2
入力
4 1
3 9 1 5
4
出力
-1

$X, Y$ に共通する整数が存在しないので, $X_i=Y_i$ なる整数は存在しない.

サンプル3
入力
10 7
3 4 10 8 19 1 12 39 2 5
8 100 3 38 29 4 11
出力
31

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