G - Sum of Pow of Mod of Linear 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MiB

配点 : 625 点

問題文

整数 N,M,A,B,X,R が与えられます。

\displaystyle \sum_{k=0}^{N-1} X^{(Ak+B) \bmod M} を R で割ったあまりを求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1\le T\le 100
  • 1\le N,M,R\le 10^9
  • 0\le A,B < M
  • 1\le X < R
  • 入力される値は全て整数

入力

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

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各テストケース \text{case}_i は以下の形式で与えられる。

N M A B X R

出力

T 行出力せよ。

i 行目には i 番目のテストケースについて、\displaystyle \sum_{k=0}^{N-1} X^{(Ak+B) \bmod M} を R で割ったあまりを出力せよ。

入力例 1

3
4 5 2 1 2 1000000000
777 429 33 58 1 1000000000
20251025 429429 777 1025 575757 998244353

出力例 1

15
777
445271630

1 つ目のテストケースについて考えます。

  • k=0 のとき： \displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 0+1) \bmod 5}=2^1=2 です。
  • k=1 のとき： \displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 1+1) \bmod 5}=2^3=8 です。
  • k=2 のとき： \displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 2+1) \bmod 5}=2^0=1 です。
  • k=3 のとき： \displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 3+1) \bmod 5}=2^2=4 です。

以上より、求める値は 2+8+1+4 を 1000000000 で割ったあまりである 15 です。したがって、 1 行目には 15 を出力してください。

Score : 625 points

Problem Statement

You are given integers N,M,A,B,X,R.

Find the remainder when \displaystyle \sum_{k=0}^{N-1} X^{(Ak+B) \bmod M} is divided by R.

You are given T test cases, so find the answer for each of them.

Constraints

  • 1\le T\le 100
  • 1\le N,M,R\le 10^9
  • 0\le A,B < M
  • 1\le X < R
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case \text{case}_i is given in the following format:

N M A B X R

Output

Print T lines.

On the i-th line, print the remainder when \displaystyle \sum_{k=0}^{N-1} X^{(Ak+B) \bmod M} is divided by R for the i-th test case.

Sample Input 1

3
4 5 2 1 2 1000000000
777 429 33 58 1 1000000000
20251025 429429 777 1025 575757 998244353

Sample Output 1

15
777
445271630

Consider the first test case.

  • When k=0: \displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 0+1) \bmod 5}=2^1=2.
  • When k=1: \displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 1+1) \bmod 5}=2^3=8.
  • When k=2: \displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 2+1) \bmod 5}=2^0=1.
  • When k=3: \displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 3+1) \bmod 5}=2^2=4.

From the above, the desired value is the remainder when 2+8+1+4 is divided by 1000000000, which is 15. Therefore, print 15 on the 1st line.