某知名 OJ 的模拟赛第一题
本帖最后由 zhangjinxuan 于 2024-7-10 21:55 编辑题目描述
你需要做出一个药水，要用纯净水和魔法水做出 x:y 的比例(当然，这两种液体可以相互溶解）。
然而，你只有一个刻有模糊刻度线的量杯。更具体地说，量杯的容积为 a+b 毫升，只有一个明显的刻度标记，即 a 毫升。也就是说，她只能通过这个量杯精确地测量出 a 毫升或 a+b 毫升的液体。
现在你可以随时进行以下操作：
1.在量杯中注入纯净水或魔法水。
2.从量杯中倒出混合水，在量杯中保留 a毫升混合水。
要使混合物的比例为 x:y，操作1的最少次数是多少？或者说这是不可能的（这时候输出 -1）。
有 T 组测试数据，每行有 4 个整数表示 x,y,a,b(保证都在 long long范围内)。
请对于每一组测试数据输出答案
样例输入与输出
4
3 5 1 1
1 24 1 4
12 113 3 2
8 117 2 3
4
3
-1
4
对于样例 1的第一组数据，首先加满纯净水 ，此时比例为 1:0；使用倒出操作，再加入魔法水 ，此时比例 1:1；使用倒出操作，再加入纯净水 ，此时比例 3:1；使用倒出操作，再加入魔法水，此时比例 3:5。共 4 次第一种操作。
看题解没看懂，std 也写得很答辩，希望得到清晰的解答。 好的！让我们来解决这个有趣的问题。我会尽量用简单易懂的方式解释。
### 题目解析
假设有两个水，纯净水和魔法水，你需要将它们混合成一定的比例 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` 比例。
具体详细实现如下：
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
def solve(x, y, a, b):
g = gcd(x, y)
x //= g
y //= g
if not gcd(a, b) == 1:
return -1
from math import ceil
min_operations = ceil(max(x / a, y / b))
return min_operations
T = int(input())
for _ in range(T):
x, y, a, b = map(int, input().split())
result = solve(x, y, a, b)
print(result)
### 问题分解
对于每个测试数据，你需要：
1. 读取输入值 x, y, a, b。
2. 利用最大公约数 gcd 分解 x 和 y。
3. 检查 gcd(a, b) 是否是1，因为它说明了量杯 a 和 a+b 可以组成任何整数。
### 最后，幽默一下
"好吧，别看这题像魔法学校的炼药课，其实就是在玩水！只要合理安排时间，每天做个好单调的实验，就能轻松搞定这杯神奇的药水啦！"
希望这个解答能帮到你！加油，祝你成功地炼制出神奇的药水！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 题目在哪？ 我们可以发现，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 时，一定成立。
剩下的就不知道了，但感觉这个思路应该可以{:10_256:} sfqxx 发表于 2024-7-11 14:15
题目在哪？
https://codeforces.com/gym/103729/problem/C tommyyu 发表于 2024-7-12 21:55
我们可以发现，1、2操作必然是交替进行，不妨将一轮“1-2”操作记为一个循环。
对于在烧杯中一杯满的液体 ...
感觉和进制有关，毕竟每一次都是 a+b 为被除数，然后原最近找到了，https://codeforces.com/gym/103729/problem/C 我tm在洛谷找 zhangjinxuan 发表于 2024-7-12 22:26
感觉和进制有关，毕竟每一次都是 a+b 为被除数，然后原最近找到了，https://codeforces.com/gym/103729 ...
《小马宝莉》 你有思路了么{:10_269:} tommyyu 发表于 2024-7-15 20:27
你有思路了么
好像先要约分再约去一个因数
页:
[1]