分数: 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第行,打印余数 \displaystyle \sum_{k=0}^{N-1} X^{(Ak+B) \bmod M} 除以 R 为 i- 第一个测试用例。
示例输入 1
3 4 5 2 1 2 1000000000 777 429 33 58 1 1000000000 20251025 429429 777 1025 575757 998244353
示例输出 1
15 777 445271630
考虑第一个测试用例。
- 当 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。因此,打印 15 上 1st线。