3674 . [模板題] Sum of Floor of Linear
TopCoder
Tags
Description
Each test case consists of $T$ cases.
Given $N, M, A, B$. Print $\sum_ {i = 0}^ {N - 1} floor((A \times i + B) / M)$.
Input Format
$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}$
Output Format
Sample Input 1
5 4 10 6 3 6 5 4 3 1 1 0 0 31415 92653 58979 32384 1000000000 1000000000 999999999 999999999
Sample Output 1
3 13 0 314095480 499999999500000000
Hints
- $1 \leq T \leq 100,000$
- $1 \leq N, M \leq 10^ 9$
- $0 \leq A, B < M$
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|