A5175. “简单”数学题
编程题
省选/NOI-
知识点
题目描述
给定整数 $A$、$B$、$C$、$D$，请你求出有多少个正整数 $i$ 满足以下条件：
- 对于所有在 $A + B \times i$ 到 $A + C \times i$（包含端点）之间的整数，这些数都不是 $D$ 的倍数。
根据题目限制，可以证明答案是有限的。
- 对于所有在 $A + B \times i$ 到 $A + C \times i$（包含端点）之间的整数，这些数都不是 $D$ 的倍数。
根据题目限制，可以证明答案是有限的。
输入格式
* 第一行包含一个整数 $T$（测试用例数量）。
* 接下来 $T$ 行，每行包含四个整数 $A, B, C, D$。
* 接下来 $T$ 行，每行包含四个整数 $A, B, C, D$。
输出格式
第 $i$ 行输出第 $i$ 个测试用例（$A_i$，$B_i$，$C_i$，$D_i$）的答案。
输入输出样例
输入 #1
2 3 1 2 5 99 101 103 105
输出 #1
1 25
说明/提示
### 限制条件
- $1 \leq T \leq 10{,}000$
- $1 \leq A < D$
- $0 \leq B < C < D$
- $2 \leq D \leq 10^8$
### 样例解释 1
对于第 $1$ 个测试用例，枚举 $(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)$
- $1 \leq T \leq 10{,}000$
- $1 \leq A < D$
- $0 \leq B < C < D$
- $2 \leq D \leq 10^8$
### 样例解释 1
对于第 $1$ 个测试用例，枚举 $(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)$