分数: 1700 点
问题陈述
给你一对非负整数 a = (a_1,a_2) 和 b = (b_1,b_2)。 您可以对该对执行以下操作 a 任意次数,可能为零。
- 操作:选择一个 正实数 x。更换 a = (a_1,a_2) 与 (\lfloor a_1x\rfloor, \lfloor a_2x\rfloor).
你的目标是使这对 a 等于该对 b。确定是否可以实现。如果是,请找出为实现该目标而必须执行该操作的最少次数。
你有 T 测试用例解决。
约束
- 1\leq T\leq 10^5
- 0\leq a_1, a_2, b_1, b_2 \leq 10^9
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
a_1 a_2 b_1 b_2
输出
打印 T 行。的 i- 第行应包含 -1 如果不可能 a 等于 b 在 i-第一个测试用例,否则为实现目标必须执行的操作的最小次数。
示例输入 1
7 2 3 1 1 1 1 2 3 3 2 9 8 12 34 56 78 56 78 12 34 87 65 43 21 43 21 87 65
示例输出 1
1 -1 3 -1 4 2 -1
对于第一个测试用例,这是一个最佳解决方案。
- 最初, a = (2,3).
- 执行操作 x = 0.6,替换 a 与 (\lfloor 1.2 \rfloor, \lfloor 1.8\rfloor) = (1,1).
对于第三个测试用例,这是一个最佳解决方案。
- 最初, a = (3,2).
- 执行操作 x = 1.5,替换 a 与 (4,3).
- 执行操作 x = 1.7,替换 a 与 (6,5).
- 执行操作 x = 1.6,替换 a 与 (9,8).
示例输入 2
9 5 5 5 5 5 5 3 3 3 9 0 2 3 9 0 3 0 3 3 9 3 0 2 0 5 2 0 0 0 0 5 2 0 0 0 0
示例输出 2
0 1 1 2 -1 1 1 -1 0