题解

思路推导

设整个过程中倒满 B 杯 $P_b$ 次、倒空 A 杯 $P_a$ 次，并在最后让 B 杯为空。此时 A 杯中的酒量为

所有可得到体积都是 $\gcd(a,b)$ 的倍数，而按辗转相减过程可以得到 $\gcd(a,b)$，所以最小正体积为 $c=\gcd(a,b)$。

做法

令 $A=a/c$、$B=b/c$，则需要求非负整数解

当 $A=1$ 时，必有 $a=b$，直接取 $P_a=0,P_b=1$。否则用扩展欧几里得算法求 $B$ 在模 $A$ 下的最小正逆元，作为 $P_b$。再由等式计算

模 $A$ 的其他正解都使 $P_b$ 增加 $A$、$P_a$ 增加 $B$，因此上述解先使 $P_a$ 最小，也随之使 $P_b$ 最小。

小范围可以直接模拟倒满、倾倒和倒空的状态循环；若 $b$ 整除 $a$，一次倒满 B 杯并倒入 A 杯即可得到最小体积。

正确性证明

酒量守恒说明任一终态 A 杯酒量都可写成 $P_b b-P_a a$，故其正值至少为 $\gcd(a,b)$。Bézout 等式给出等于该最大公约数的整数线性组合，而规范后的非负解对应不断倒满 B 杯、A 杯满时倒空、继续倾倒余量的合法操作序列，所以该下界可达。

约分后的方程要求 $BP_b\equiv1\pmod A$。所取逆元是最小正代表元，所有其他非负解均同时增加固定正量，因此输出的 $P_a,P_b$ 满足题目规定的字典序最小性。

复杂度分析

时间复杂度为 $O(\log\min(a,b))$，空间复杂度为 $O(1)$。