(mod P 上の逆元について)

以降、演算 op にたいして、X op Y を mod P 上で計算した結果 Z になることを X op Y = Z (mod P) と表記します。

ここでは、べき乗計算についてやっていきます。

X ^ Y (mod P) は X を Y 回掛け合わせたものになります。つまり、for文などで繰り返し X を問題 1 と同様にかけていくことで計算が出来ますが、Y が 10 ^ 18 といったように大きくなってしまうと処理に時間がかかりすぎてしまいます。

そこで、2 進数をもとに高速に計算することを考えます。

任意の整数 K に対し、K × K = K ^ 2 (mod P) が成り立ちます。このことより繰り返し掛け合わせていくことにより、X × X = X ^ 2 (mod P)、X ^ 2 × X ^ 2 = X ^ 4 (mod P)、X ^ 4 × X ^ 4 = X ^ 8 (mod P)、... と指数が 2 のべき乗であるものが高速に計算できます。これらを組み合わせることにより任意の Y について、X ^ Y について計算することを考えます。

Y を 2 進数表記で考えます。そのとき Y = y_Ly_{L-1}...y_0 (y_i は 0 か 1)と 2 進数表記で表せたとします。そのとき Y は y_L,y_{L-1},...,y_0 を用いて、Y = y_L × 2 ^ L + y_{L-1} × 2 ^ {L - 1} + ... + y_0 × 2 ^ 0 と 2 のべき乗と y_i の掛け算で表すことが出来ます。

よって、X ^ Y = X ^ {y_L × 2 ^ L × y_{L-1} × 2 ^ {L - 1} × ... × y_{0} × 2 ^ 0} = X ^ {y_L × 2 ^ L} × X ^ {y_{L-1} × 2 ^ {L - 1}} × ... × X ^ {y_0 × 2 ^ 0} (mod P) となります。y_i は 0 か 1 であり、y_i = 0 のときには、X ^ 0 = 1 を、y_i = 1 のときには、X ^ {2 ^ i} をそれぞれ掛け合わせてあげればいいことがわかります。

例として、3 ^ 13 (mod 17) を計算します。3 ^ 1 = 3 (mod 17)、3 ^ 2 = 3 × 3 = 9 (mod 17)、3 ^ 4 = 9 × 9 = 13 (mod 17)、3 ^ 8 = 13 × 13 = 16 (mod 17) と計算でき 13 を 2 進数表記すると 1101 なので、3 ^ 13 = 3 ^ 8 × 3 ^ 4 × 3 ^ 1 = 16 × 13 × 3 = 12 (mod 17) と計算が出来ます。

この方法は繰り返し二乗法とよび、log_2 Y 回程度で計算することが出来ます。10 ^ 18 < 2 ^ 64 により、Y が 10 ^ 18 ととてつもなく大きかったとしても、高速に計算が出来ることがわかります。

では実際に計算してみましょう。

(問題)

素数 P が与えられます。 Q 個のクエリが与えられるので、順番に処理してください。i (1 ≦ i ≦ Q) 番目のクエリは以下の通りです。

X_i ^ Y_i (mod P) を出力する。