[ABC443G] Another Mod of Linear Problem（另一种线性同余问题）

题目描述

给定整数 $N, M, A, B$。

定义整数序列 $X = (X_0, X_1, \ldots, X_{N-1})$，其中

求满足 $0 \le k < N$ 且 $X_k > k$ 的整数 $k$ 的个数。

给定 $T$ 组测试数据，请分别求解。

输入格式

输入从标准输入按以下格式给出：

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

每组测试数据格式如下：

$N$ $M$ $A$ $B$

输出格式

按顺序输出每组测试数据的答案，每个答案占一行。

输入输出样例 #1

输入 #1

4
4 6 4 3
7 7 3 1
10 46 0 12
443 2026 131 210

输出 #1

2
3
10
395

说明/提示

样例解释 1

考虑第一组测试数据：

• 当 $k=0$：$X_0 = (4 \times 0 + 3) \bmod 6 = 3$，满足 $X_k > k$；
• 当 $k=1$：$X_1 = (4 \times 1 + 3) \bmod 6 = 1$，不满足 $X_k > k$；
• 当 $k=2$：$X_2 = (4 \times 2 + 3) \bmod 6 = 5$，满足 $X_k > k$；
• 当 $k=3$：$X_3 = (4 \times 3 + 3) \bmod 6 = 3$，不满足 $X_k > k$。

因此，满足条件的 $k$ 为 $0$ 和 $2$，共 2 个，故第一行输出 $2$。

约束条件

• $1 \le T \le 3 \times 10^5$
• $1 \le N \le M \le 10^9$
• $0 \le A, B < M$
• 所有输入值均为整数。