分数: 575 点
问题陈述
给你整数 N,M,A,B.
定义一个整数序列 X=(X_0,X_1,\ldots,X_{N-1}) as \displaystyle X_k = (Ak+B) \bmod M.
查找整数的个数 k 满意 0 \le k < N 和 X_k > k.
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1\le T\le 3\times 10^5
- 1\le N \le M\le 10^9
- 0\le A,B < M
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N M A B
输出
按顺序输出测试用例的答案,以换行符分隔。
样本输入 1
4 4 6 4 3 7 7 3 1 10 46 0 12 443 2026 131 210
示例输出 1
2 3 10 395
考虑第一个测试用例。
- 当 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 \le k < 4 和 X_k>k 是 k=0,2,这是两个整数。因此,输出 2 在第一行。