Sum of Floor of Linear

AC一覧

Problem Statement
問題文

Each test case consists of $T$ cases.

Given $N, M, A, B$. Print $\sum_{i = 0}^{N - 1} floor((A \times i + B) / M)$.

この問題は $T$ ケース与えられます。

$N, M, A, B$ が与えられます。

$\sum_{i = 0}^{N - 1} floor((A \times i + B) / M)$ を求めてください。

Constraints
制約

Input
入力

$T$
$N_0$ $M_0$ $A_0$ $B_0$
$N_1$ $M_1$ $A_1$ $B_1$
:
$N_{T - 1}$ $M_{T - 1}$ $A_{T - 1}$ $B_{T - 1}$

Sample
サンプル

# 1

5
4 10 6 3
6 5 4 3
1 1 0 0
31415 92653 58979 32384
1000000000 1000000000 999999999 999999999
3
13
0
314095480
499999999500000000

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions