← 返回题目列表

AtCoder · abc443_g

G. 线性问题的另一种模式

中文机器翻译题面 查看原题

分数: 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 在第一行。