東京海上日動プログラミングコンテスト2025（AtCoder Beginner Contest 402）
翻译中…
Problem Statement
翻译中…
You are given integers $N,M,A,B_1,B_2$.
翻译中…
Find $\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$.
翻译中…
There are $T$ test cases; solve each one.
翻译中…
Constraints
翻译中…
$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$- 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翻译中…
Here, $\text{case}_i$ denotes the $i$-th test case.
翻译中…
Each test case is given in the following format:
翻译中…
N M A B_1 B_2翻译中…
Output
翻译中…
Print $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.
翻译中…
样例
Input #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
Output #1
27
866
0
1000000
13728568
Consider the first test case.
- When $k=0$: $\left\lbrace (2k+1)\ \text{mod}\ 7 \right\rbrace=1,\ \left\lbrace (2k+4)\ \text{mod}\ 7 \right\rbrace=4$.
- When $k=1$: $\left\lbrace (2k+1)\ \text{mod}\ 7 \right\rbrace=3,\ \left\lbrace (2k+4)\ \text{mod}\ 7 \right\rbrace=6$.
- When $k=2$: $\left\lbrace (2k+1)\ \text{mod}\ 7 \right\rbrace=5,\ \left\lbrace (2k+4)\ \text{mod}\ 7 \right\rbrace=1$.
- When $k=3$: $\left\lbrace (2k+1)\ \text{mod}\ 7 \right\rbrace=0,\ \left\lbrace (2k+4)\ \text{mod}\ 7 \right\rbrace=3$.
Hence, the required value is $1\times 4+3\times 6+5\times 1+0\times 3=27$. Thus, print $27$ on the first line.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。