题目详情题解（0）讨论（0）提交记录（0）

AT_abc429_g.[ABC429G] Sum of Pow of Mod of Linear

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定整数 N,M,A,B,X,RN, M, A, B, X, R。

求 ∑k=0N−1X(Ak+B) mod M\displaystyle \sum_{k=0}^{N-1} X^{(Ak+B) \bmod M} 被 RR 除后的余数。

给定 TT 组测试数据，请分别输出每组的答案。

输入格式

输入通过标准输入给出，格式如下：

T case1 case2 ⋮ caseTT\ \text{case}_1\ \text{case}_2\ \vdots\ \text{case}_T

每组测试数据 casei\text{case}_i 的格式为：

N M A B X RN\ M\ A\ B\ X\ R

输出格式

输出 TT 行。

第 ii 行输出第 ii 组测试数据下 ∑k=0N−1X(Ak+B) mod M\displaystyle \sum_{k=0}^{N-1} X^{(Ak+B)\bmod M} 被 RR 除后的余数。

输入输出样例

  • 输入#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=0k=0 时：X(Ak+B) mod M=2(2×0+1) mod 5=21=2X^{(Ak+B)\bmod M}=2^{(2\times 0+1)\bmod 5}=2^1=2。
  • 当 k=1k=1 时：X(2×1+1) mod 5=23=8X^{(2\times 1+1)\bmod 5}=2^3=8。
  • 当 k=2k=2 时：X(2×2+1) mod 5=20=1X^{(2\times 2+1)\bmod 5}=2^0=1。
  • 当 k=3k=3 时：X(2×3+1) mod 5=22=4X^{(2\times 3+1)\bmod 5}=2^2=4。

由上可知，所需的值是 2+8+1+42+8+1+4 被 10000000001000000000 除后的余数，即 1515。因此，第 11 行输出 1515。

数据范围

  • 1≤T≤1001\le T\le 100
  • 1≤N,M,R≤1091\le N,M,R\le 10^9
  • 0≤A,B<M0\le A,B < M
  • 1≤X<R1\le X < R
  • 所有输入均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页