问题:假设你有一个3升的容器和一个5升的容器(以及充足的水源),如何精确地取出4升水来?(为了下文叙述的方便,我们不妨把3升的容器和5升的容器分别记做容器A和容器B)。这里提供一种解法:
- 将A装满(3升),全部倒入B
- 再次将A装满(3升),用A中的水将B装满,此时A有1升,B有5升
- B中的水全部倒出,将A中的1升水倒入B,此时A没有水,B有一升
- 再次将A装满(3升),将A中的水全部倒入B,此时B中恰有4升的水
显然这类问题可以有其他的解决方案。我们可轻易地编出其他类似的问题,比如是否能够用7升的水杯和13升的水杯量出5升的水,再比如能否用9升的水杯和15升的水杯量出10升的水,不胜枚举。三升五升得四升的问题还算直观,稍作思考便可构造解决方案。7升13升得5升,似乎就没那么直观了。而且还有一个问题,首先需要判断是否可行,然后才是给出解决方案。
这样的问题存在一个万能的解法吗?答案是肯定的。注意到,用3升的容器和5升的容器量出4升的水,这一看似复杂的步骤可以简单地概括为:不断地将整杯整杯的A往B里倒,期间只要B被装满就把B倒空。即求解
接着看 7 升 13 升得 5 升,也即
第一步,首先来看贝祖等式时的情况,也即
第二步,
- 将装满 7 升水的 A 倒入 B ⇒ A(0升),B(7升)
- 将装满7升水的 A 倒入 B,直到 B 加满为止 ⇒ A(1升),B(13升)
- 将 B 清空,⇒ A (1升),B(0升)
- 将 A 中的一升水倒入 B,⇒ A(0升),B(1升)(1,2,3,4 步为一个单元)
- 将 A 加满倒入 B,⇒ A(0升),B(8升)
- 再次将 A 加满倒入 B,直到 B 满为止,⇒ A(2升),B(13升)
- 将 B 清空,⇒ A(2升),B(0升)
- 将 A 中的 2 升水倒入 B,⇒ A(0升),B(2升)
。。。
直到 A(5升),B(0升);
我们进一步将问题抽象,用容积分别为
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