← 返回题目列表

AtCoder · abc429_g

G. 线性模的 Pow 总和

中文机器翻译题面 查看原题

分数: 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线。