分数: 100 点
问题陈述
在这个问题中,你应该处理 T 测试用例。
对于每个测试用例,您将获得四个整数 N, M, A, B.
计算 \sum_{i = 0}^{N - 1} floor((A \times i + B) / M).
约束
- 1 \leq T \leq 100,000
- 1 \leq N, M \leq 10^9
- 0 \leq A, B < M
输入
输入由标准输入按以下格式给出:
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}
输出
打印每个测试用例的答案。
示例输入 1
5 4 10 6 3 6 5 4 3 1 1 0 0 31415 92653 58979 32384 1000000000 1000000000 999999999 999999999
示例输出 1
3 13 0 314095480 499999999500000000