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

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

1. 将A装满（3升），全部倒入B
2. 再次将A装满（3升），用A中的水将B装满，此时A有1升，B有5升
3. B中的水全部倒出，将A中的1升水倒入B，此时A没有水，B有一升
4. 再次将A装满（3升），将A中的水全部倒入B，此时B中恰有4升的水

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

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

接着看 7 升 13 升得 5 升，也即 7xmod13=5 <script id="MathJax-Element-67" type="math/tex">7x\mod 13=5</script>， 7,13 <script id="MathJax-Element-68" type="math/tex">7,13</script> 互质，首先判断有解，即存在这样一个解决方案。这个方案是怎样的呢？

第一步，首先来看贝祖等式时的情况，也即 7xmod13=1 <script id="MathJax-Element-69" type="math/tex">7x\mod 13=1</script>时，此时解得 x=2 <script id="MathJax-Element-70" type="math/tex">x=2</script>，也即 2 个 A 倒入 B，A余一升（得1升）

第二步， 7xmod13=5 <script id="MathJax-Element-71" type="math/tex">7x \mod 13=5</script>，此时 x=(2×5)%13=10 <script id="MathJax-Element-72" type="math/tex">x= (2\times 5)\%13=10</script>，也即对第一步的行为执行五次，如下：

1. 将装满 7 升水的 A 倒入 B ⇒ A（0升），B（7升）
2. 将装满7升水的 A 倒入 B，直到 B 加满为止 ⇒ A（1升），B（13升）
3. 将 B 清空，⇒ A （1升），B（0升）
4. 将 A 中的一升水倒入 B，⇒ A（0升），B（1升）（1,2,3,4 步为一个单元）
5. 将 A 加满倒入 B，⇒ A（0升），B（8升）
6. 再次将 A 加满倒入 B，直到 B 满为止，⇒ A（2升），B（13升）
7. 将 B 清空，⇒ A（2升），B（0升）
8. 将 A 中的 2 升水倒入 B，⇒ A（0升），B（2升）
   。。。
   直到 A（5升），B（0升）；

我们进一步将问题抽象，用容积分别为 a <script id="MathJax-Element-73" type="math/tex">a</script> 和 b<script id="MathJax-Element-74" type="math/tex">b</script> 的水杯量出体积为 c <script id="MathJax-Element-75" type="math/tex">c</script> 的水，实际上相当于求解方程 a⋅xmodb=c<script id="MathJax-Element-76" type="math/tex">a\cdot x\mod b=c</script>。如果 a,b <script id="MathJax-Element-77" type="math/tex">a,b</script> 互质，问题保证有解。如果 c==gcd(a,b) <script id="MathJax-Element-78" type="math/tex">c==gcd(a,b)</script> 或者 c==k⋅gcd(a,b) <script id="MathJax-Element-79" type="math/tex">c==k\cdot gcd(a,b)</script>，用扩展欧几里得算法便可求解 x <script id="MathJax-Element-80" type="math/tex">x</script>，然后得最终的量水方案。如果 c<script id="MathJax-Element-81" type="math/tex">c</script> 不能被 gcd(a,b) <script id="MathJax-Element-82" type="math/tex">gcd(a,b)</script> 整除，方程无解，也即问题无解，比如9升15升的容器得10升的水， 10 <script id="MathJax-Element-83" type="math/tex">10</script> 不能被 gcd(9,15)=3 <script id="MathJax-Element-84" type="math/tex"> gcd(9,15)=3</script> 整除。

def ext_euclid(a, b):
                    # 扩展的欧几里得算法
                    # 用以求解
                    # d = gcd(a, b) = a*x+b*y
    if b == 0:
        return (a, 1, 0)
    d, x, y = ext_euclid(b, a%b)
    return (d, y, x-a//b*y)

def mod_linear_equation(a, b, c):
    d, x, y = ext_euclid(a, b)
    if c % d:
        raise 'no solution'
    return x * c//d % b

if __name__ == '__main__':
    print(mod_linear_equation(3, 5, 4))
                # 3
    print(mod_linear_equation(7, 13, 5))
                # 10