問題一覧 > 通常問題

No.2362 Inversion Number of Mod of Linear

レベル : / AI推定難易度 : 2375 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 13
作問者 : 👑 qand / テスター : LayCurse ygussany
お気に入りにしたユーザー ProblemId : 9601 / 自分の提出
問題文最終更新日: 2023-06-23 17:01:19
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 394 (順位表) の他の問題:

Problem Statement

Define an integer sequence $A=(A_0,A_1,\ldots,A_{N-1})$ of length $N$ by $A_i=(iX+Y)\ \text{mod}\ M$.

Find the inversion number of this integer sequence $A$.

You are given $T$ test cases; find the answer for each of them.

What is $(iX+Y)\ \text{mod}\ M$?

There exists exactly one integer $C$ that is at least $0$ and less than $M$ such that $iX+Y-C$ is a multiple of $M$. The value of this $C$ is denoted by $(iX+Y)\ \text{mod}\ M$.

What is the inversion number of $A$?

It is the number of pairs of integers $(i,j)$ satisfying all of the following conditions.

  • $0\le i < j < N$
  • $A_i > A_j$

Constraints

  • $1\le T\le 10^4$
  • $1\le N,M\le 10^9$
  • $0\le X,Y < M$

Input

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$
The $i$-th test case $\text{case}_i$ is given in the following format. 
$N$ $M$ $X$ $Y$

Output

Print $T$ lines.

On the $i$-th line $(1\le i\le T)$, print the answer for $\text{case}_i$.

Sample

Sample 1
Input
2
5 7 2 2
4 5 3 2
Output
5
3

In test case number $1$, $A=(2,4,6,1,3)$. The inversion number of this integer sequence is $5$, so print $5$.

In test case number $2$, $A=(2,0,3,1)$. The inversion number of this integer sequence is $3$, so print $3$.

Sample 2
Input
1
1000000 15 3 9
Output
200000200000

The answer can be very large.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。