分数: 800 点
问题陈述
在这个问题中,你将得到 T 每个输入的测试用例。
给定整数 A, B, C,和 D,查找正整数的个数 i 满足以下条件:
- 之间没有任何整数 A + B \times i 和 A + C \times i (含)是以下的倍数 D.
我们可以从约束证明计数是有限的。
约束
- 1 \leq T \leq 10{,}000
- 1 \leq A < D
- 0 \leq B < C < D
- 2 \leq D \leq 10^8
输入
输入由标准输入按以下格式给出:
T A_1 B_1 C_1 D_1 : A_T B_T C_T D_T
输出
打印 T 行。
的 i- 第行应包含以下问题的答案 i第一个案例 (A_i, B_i, C_i, D_i).
示例输入 1
2 3 1 2 5 99 101 103 105
示例输出 1
1 25
对 下面列出了第一种情况的 (A + B \times i, A + C \times i) 。我们可以看到,只有 i = 3 满足条件。
- i = 1: (4, 5)
- i = 2: (5, 7)
- i = 3: (6, 9)
- i = 4: (7, 11)
- i = 5: (8, 13)
- :