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 翻译