← 返回题目列表

AtCoder · arc111_e

E. 简单数学 3

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

分数: 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)
  • :