AT_abc443_g [ABC443G] Another Mod of Linear Problem

给定整数 $N, M, A, B$。 定义整数序列 $X=(X_0, X_1, \ldots, X_{N-1})$，其中 $X_k = (A k + B) \bmod M$。 求满足 $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 以第一组测试数据为例。 - 当 $k=0$ 时：$X_0 = (4 \times 0 + 3) \bmod 6 = 3$，此时 $X_0 > k$ 成立。 - 当 $k=1$ 时：$X_1 = (4 \times 1 + 3) \bmod 6 = 1$，此时 $X_1 > k$ 不成立。 - 当 $k=2$ 时：$X_2 = (4 \times 2 + 3) \bmod 6 = 5$，此时 $X_2 > k$ 成立。 - 当 $k=3$ 时：$X_3 = (4 \times 3 + 3) \bmod 6 = 3$，此时 $X_3 > k$ 不成立。 由此可知，满足 $0 \le k < 4$ 且 $X_k > 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$ - 所有输入值均为整数。 由 ChatGPT 5 翻译