"3升5升得4升"

扩展欧几里得算法及其应用

问题：假设你有一个3升的容器和一个5升的容器（以及充足的水源），如何精确地取出4升水来？（为了下文叙述的方便，我们不妨把3升的容器和5升的容器分别记做容器A和容器B）。这里提供一种解法：

显然这类问题可以有其他的解决方案。我们可轻易地编出其他类似的问题，比如是否能够用7升的水杯和13升的水杯量出5升的水，再比如能否用9升的水杯和15升的水杯量出10升的水，不胜枚举。三升五升得四升的问题还算直观，稍作思考便可构造解决方案。7升13升得5升，似乎就没那么直观了。而且还有一个问题，首先需要判断是否可行，然后才是给出解决方案。

这样的问题存在一个万能的解法吗？答案是肯定的。注意到，用3升的容器和5升的容器量出4升的水，这一看似复杂的步骤可以简单地概括为：不断地将整杯整杯的A往B里倒，期间只要B被装满就把B倒空。即求解 3xmod5=4 ，使用 扩展欧几里得算法及其应用 一文的算法我们可轻易解得 x=3 。首先根据扩展欧几里得算法，问题有解。 x=3 时，对应的解决方案见上文。

接着看 7 升 13 升得 5 升，也即 7xmod13=5 ， 7,13 互质，首先判断有解，即存在这样一个解决方案。这个方案是怎样的呢？

第一步，首先来看贝祖等式时的情况，也即 7xmod13=1 时，此时解得 x=2 ，也即 2 个 A 倒入 B，A余一升（得1升）

第二步， 7xmod13=5 ，此时 x=(2×5)%13=10 ，也即对第一步的行为执行五次，如下：

我们进一步将问题抽象，用容积分别为 a 和 b 的水杯量出体积为 c 的水，实际上相当于求解方程 a⋅xmodb=c。如果 a,b 互质，问题保证有解。如果 c==gcd(a,b) 或者 c==k⋅gcd(a,b) ，用扩展欧几里得算法便可求解 x ，然后得最终的量水方案。如果 c 不能被 gcd(a,b) 整除，方程无解，也即问题无解，比如9升15升的容器得10升的水， 10 不能被 gcd(9,15)=3 整除。