AT_abc429_g [ABC429G] Sum of Pow of Mod of Linear

给定整数 $N, M, A, B, X, R$。 求 $\displaystyle \sum_{k=0}^{N-1} X^{(Ak+B) \bmod M}$ 被 $R$ 除后的余数。 给定 $T$ 组测试数据，请分别输出每组的答案。

输入通过标准输入给出，格式如下： > $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 考虑第一组测试数据。 - 当 $k=0$ 时：$X^{(Ak+B)\bmod M}=2^{(2\times 0+1)\bmod 5}=2^1=2$。 - 当 $k=1$ 时：$X^{(2\times 1+1)\bmod 5}=2^3=8$。 - 当 $k=2$ 时：$X^{(2\times 2+1)\bmod 5}=2^0=1$。 - 当 $k=3$ 时：$X^{(2\times 3+1)\bmod 5}=2^2=4$。 由上可知，所需的值是 $2+8+1+4$ 被 $1000000000$ 除后的余数，即 $15$。因此，第 $1$ 行输出 $15$。 ### 数据范围 - $1\le T\le 100$ - $1\le N,M,R\le 10^9$ - $0\le A,B < M$ - $1\le X < R$ - 所有输入均为整数。 由 ChatGPT 5 翻译