← 返回题目列表

AtCoder · abc402_g

G. 线性模的乘积之和

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

分数: 650 点

问题陈述

给你整数 N,M,A,B_1,B_2.

查找 \displaystyle\sum_{k=0}^{N-1}\left\lbrace (Ak+B_1)\ \text{mod}\ M \right\rbrace\left\lbrace (Ak+B_2)\ \text{mod}\ M \right\rbrace.

有 T 测试用例;逐一解决。

约束

  • 1\le T\le 10^5
  • 1\le N\le 10^6
  • 1\le M\le 10^6
  • 0\le A,B_1,B_2 < M
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

在这里, \text{case}_i 表示 i- 第一个测试用例。

每个测试用例均按以下格式给出:

N M A B_1 B_2

输出

打印 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。


示例输入 1

5
4 7 2 1 4
12 15 2 8 7
777 1 0 0 0
100 101 0 100 100
402 402 4 19 256

示例输出 1

27
866
0
1000000
13728568

考虑第一个测试用例。

  • 当 k=0: \left\lbrace (2k+1)\ \text{mod}\ 7 \right\rbrace=1,\ \left\lbrace (2k+4)\ \text{mod}\ 7 \right\rbrace=4.
  • 当 k=1: \left\lbrace (2k+1)\ \text{mod}\ 7 \right\rbrace=3,\ \left\lbrace (2k+4)\ \text{mod}\ 7 \right\rbrace=6.
  • 当 k=2: \left\lbrace (2k+1)\ \text{mod}\ 7 \right\rbrace=5,\ \left\lbrace (2k+4)\ \text{mod}\ 7 \right\rbrace=1.
  • 当 k=3: \left\lbrace (2k+1)\ \text{mod}\ 7 \right\rbrace=0,\ \left\lbrace (2k+4)\ \text{mod}\ 7 \right\rbrace=3.

因此,所需的值为 1\times 4+3\times 6+5\times 1+0\times 3=27。因此,打印 27 在第一行。