/ 
Time Limit: 4 sec / Memory Limit: 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.