[已解决]某知名 OJ 的模拟赛第一题

zhangjinxuan

题目描述

你需要做出一个药水，要用纯净水和魔法水做出 x:y 的比例(当然，这两种液体可以相互溶解）。

然而，你只有一个刻有模糊刻度线的量杯。更具体地说，量杯的容积为 a+b 毫升，只有一个明显的刻度标记，即 a 毫升。也就是说，她只能通过这个量杯精确地测量出 a 毫升或 a+b 毫升的液体。

现在你可以随时进行以下操作：

1.在量杯中注入纯净水或魔法水。
2.从量杯中倒出混合水，在量杯中保留 a毫升混合水。

要使混合物的比例为 x:y，操作1的最少次数是多少？或者说这是不可能的（这时候输出 -1）。

有 T 组测试数据，每行有 4 个整数表示 x,y,a,b(保证都在 long long  范围内)。

请对于每一组测试数据输出答案

样例输入与输出

1. 4
   
2. 3 5 1 1
   
3. 1 24 1 4
   
4. 12 113 3 2
   
5. 8 117 2 3

复制代码

1. 4
   
2. 3
   
3. -1
   
4. 4

复制代码

对于样例 1  的第一组数据，首先加满纯净水 ，此时比例为 1:0；使用倒出操作，再加入魔法水 ，此时比例 1:1；使用倒出操作，再加入纯净水 ，此时比例 3:1；使用倒出操作，再加入魔法水，此时比例 3:5。共 4 次第一种操作。


看题解没看懂，std 也写得很答辩，希望得到清晰的解答。

最佳答案

月排行榜 / 总排行榜

tommyyu

2024-7-12 21:55:58

我们可以发现，1、2操作必然是交替进行，不妨将一轮“1-2”操作记为一个循环。
对于在烧杯中一杯满的液体，记其中魔法水的浓度为 n (0 <= n <= 1)，则每进行一次“1-2”循环，其中液体浓度将会变为 an/(a+b) 或 (an+b)/(a+b)。n的初始值为 0 或 1。
则将问题转化为：对于给定的 x, y, a, b, n (n=0或1)，是否存在 k 次变化，每次令 n = an/(a+b) 或 n = (an+b)/(a+b)，使得最后的 n 的值等于 x/y ？
注意到，x=0，即 x/y=0 时，一定成立。
剩下的就不知道了，但感觉这个思路应该可以

跳转到最佳答案楼层

FishC

好的！让我们来解决这个有趣的问题。我会尽量用简单易懂的方式解释。

### 题目解析
假设有两个水，纯净水和魔法水，你需要将它们混合成一定的比例 x:y。你有一个特殊的量杯，它可以精确测量 a 毫升或 a+b 毫升的液体。如果不能达到目标比例，需要输出 -1。

我们的基本操作有两种：
1. **注入**：可以直接注入 a 或 a+b 毫升的任意液体。
2. **倒出**：每次保留 a 毫升的混合液体，然后再注入新的液体。

### 思路
根据题目, 每次操作中, 杯子里要么是 `a` 毫升, 要么是 `a+b` 毫升。为了使比例达到 x:y, 你需要不断地通过倒出部分液体并重新加入新液体来调整比例。

大致可以分为以下步骤：
1. 首先检查是否存在解。
2. 如果存在解，计算最少的注入次数。

### 解决办法
1. 检查是否存在解的条件: 比例 `x : y` 可以化简到一个基本形式 `(gcd(x, y) * p) : (gcd(x, y) * q)`，之后确保 `(x - y)` 可以由 `a` 和 `b` 表达出来，也就是 `x` 和 `y` 的 `gcd` 是 `a` 和 `b` 的线性组合。

2. 最小操作次数: 我们每次倒出，并重新注入另一种液体，可以保证每次变化 `a` 或 `a+b`。所以实际过程就是找一个线性组合使得最终形成 `x : y` 比例。

具体详细实现如下：

1. def gcd(a, b):
   
2.     while b != 0:
   
3.         a, b = b, a % b
   
4.     return a
   
5. 
   
6. def solve(x, y, a, b):
   
7.     g = gcd(x, y)
   
8.     x //= g
   
9.     y //= g
   
10.    
    
11.     if not gcd(a, b) == 1:
    
12.         return -1
    
13. 
    
14.     from math import ceil
    
15.     min_operations = ceil(max(x / a, y / b))
    
16.    
    
17.     return min_operations
    
18. 
    
19. T = int(input())
    
20. for _ in range(T):
    
21.     x, y, a, b = map(int, input().split())
    
22.     result = solve(x, y, a, b)
    
23.     print(result)

复制代码

### 问题分解
对于每个测试数据，你需要：
1. 读取输入值 x, y, a, b。
2. 利用最大公约数 gcd 分解 x 和 y。
3. 检查 gcd(a, b) 是否是1，因为它说明了量杯 a 和 a+b 可以组成任何整数。

### 最后，幽默一下
"好吧，别看这题像魔法学校的炼药课，其实就是在玩水！只要合理安排时间，每天做个好单调的实验，就能轻松搞定这杯神奇的药水啦！"

希望这个解答能帮到你！加油，祝你成功地炼制出神奇的药水！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

sfqxx

题目在哪？

tommyyu

我们可以发现，1、2操作必然是交替进行，不妨将一轮“1-2”操作记为一个循环。
对于在烧杯中一杯满的液体，记其中魔法水的浓度为 n (0 <= n <= 1)，则每进行一次“1-2”循环，其中液体浓度将会变为 an/(a+b) 或 (an+b)/(a+b)。n的初始值为 0 或 1。
则将问题转化为：对于给定的 x, y, a, b, n (n=0或1)，是否存在 k 次变化，每次令 n = an/(a+b) 或 n = (an+b)/(a+b)，使得最后的 n 的值等于 x/y ？
注意到，x=0，即 x/y=0 时，一定成立。
剩下的就不知道了，但感觉这个思路应该可以

zhangjinxuan

sfqxx 发表于 2024-7-11 14:15
题目在哪？

https://codeforces.com/gym/103729/problem/C

zhangjinxuan

tommyyu 发表于 2024-7-12 21:55
我们可以发现，1、2操作必然是交替进行，不妨将一轮“1-2”操作记为一个循环。
对于在烧杯中一杯满的液体 ...

感觉和进制有关，毕竟每一次都是 a+b 为被除数，然后原最近找到了，https://codeforces.com/gym/103729/problem/C

sfqxx

我tm在洛谷找

sfqxx

zhangjinxuan 发表于 2024-7-12 22:26
感觉和进制有关，毕竟每一次都是 a+b 为被除数，然后原最近找到了，https://codeforces.com/gym/103729 ...

《小马宝莉》

tommyyu

你有思路了么

zhangjinxuan

tommyyu 发表于 2024-7-15 20:27
你有思路了么

好像先要约分再约去一个因数