Sparse Table 練習問題 2 COBOL(Beta)編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ポスト
問題
下記の問題をプログラミングしてみよう！
長さ N の数列 A が与えられます。
ここで、数列の要素を 0-index で表すとします。
つまり、数列 A は A_0, A_1, ..., A_{N-1} です。
Q 個のクエリが与えられるので順に解答してください。クエリの形式は以下の通りです。
・l r：A_l, A_{l+1}, ..., A_{r-1} の最大公約数を出力する。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N Q
A_0 A_1 ... A_{N-1}
l_1 r_1
l_2 r_2
...
l_Q r_Q
・1 行目には、数列の長さを表す整数 N とクエリの数を表す整数 Q が与えられます。
・2 行目には、数列 A が空白区切りで与えられます。
・続く Q 行の i 行目には i 個目のクエリが与えられます。クエリの形式は問題文の通りです。
・入力は合計で Q+2 行からなり、入力値最終行の末尾に改行が１つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
期待する出力は Q 行からなります。
i 行目には i 個目のクエリに対する答えを出力してください。
最後は改行し、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ N ≦ 10^5
・1 ≦ Q ≦ 10^5
・1 ≦ A_i ≦ 10^9
・0 ≦ l_i < r_i ≦ N
- 入力例1
-
5 3
12 18 24 5 10
0 3
2 4
3 5
- 出力例1
-
6
1
5
- 入力例2
-
5 3
6 12 18 30 36
0 5
1 3
3 5
- 出力例2
-
6
6
6
