G - Sum of Prod of Mod of Linear Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MiB

配点 : 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

1 番目のテストケースについて考えます。

  • 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 です。したがって、 1 行目には 27 を出力してください。

Score : 650 points

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.

Sample 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

Sample 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.