Polaris.AI プログラミングコンテスト 2025（AtCoder Beginner Contest 429）
翻译中…
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.
翻译中…
样例
Input #1
3
4 5 2 1 2 1000000000
777 429 33 58 1 1000000000
20251025 429429 777 1025 575757 998244353
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 $1$st line.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。