分数: 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 在第一行。