(問題 1) mod P 上の計算 Ruby編（paizaランク C 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
(はじめに)
この問題集では、Rolling Hashというアルゴリズムを扱い高速に文字列の一致判定を行えるようにします。
まずはじめに、Rolling Hashの前提知識としてmod P 上での演算を行います。
(mod P 上の演算について)
mod P 上の演算について、はじめにやっていきます。
こちらは 0 以上 P 未満の整数のみを使って演算を完結させています。具体的には、計算結果を P で割った余りに置き換えています(割り算は例外で特殊なため問題 2 で扱います。)。
例えば、mod 5 上の演算では 3 + 4 は計算結果の 7 を 5 で割った余りである 2 となります。3 × 4 は計算結果の 12 を 5 で割った余りの 2 となります。1 - 3 も同様に計算結果を 5 で割った余りである 3 となります。
では実際に計算してみましょう。
(問題)
素数 P が与えられます。また、X = 1 で初期化された変数があります。Q 個のクエリが与えられるので、mod P 上で演算を行ってください。
- 入力される値
-
入力は以下のフォーマットで与えられます。
P Q
q_1 Y_1
q_2 Y_2
...
q_Q Y_Q- 1 行目には 2 つの整数 P,Q が与えられます。
- 1 + i (1 ≦ i ≦ Q) 行目には 2 つの整数 q_i,Y_i が与えられます。
- 入力は合計で 1 + Q 行からなり、入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
Q 行で出力してください。
i (1 ≦ i ≦ Q) 行目には i 番目のクエリの答えを出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
- 10 ^ 8 ≦ P ≦ 2 × 10 ^ 9
- 1 ≦ Q ≦ 200000
- 1 ≦ q_i ≦ 3 (1 ≦ i ≦ Q)
- 0 ≦ Y_i < P (1 ≦ i ≦ Q)
- P は素数
- 入力例1
-
998244353 3
1 12
2 15
3 19
- 出力例1
-
13
998244351
998244315
