今天无聊打开了下leetcode，看到一个新题，结论挺简单的，来证明下这个结论吧。
题目链接
题意很简单，就是两个容量分别为a和b的桶，你用他们是否可以量出体积为m的水，只能装满或者倒完。
简化一下题目其实就是下面这个式子是否有解，如果有就是true，没有就是false。
xa + yb = m, m > 0, x,y,a,b都是整数
可以在网上搜索一下这个题的题解都写的很简单m是否被gcd(a,b)整除，如果是就是true，如果不是就false。但是没有人给出了为什么（可能是吧没看到）。
设有集合S = {m = xa + yb, n > 0}，d是集合S中最小的元素 d = ua + vb
x也是S中的元素，且 x = qd + r，x不被d整除， 那么 r > 0 and r < d
r = x - qd
= xa + yb - qd
= xa + yb -q(ua + vb)
= (x - qu)a + (y-qb)b
那么r也是属于S，并且r < d和d是最小的元素这个假设矛盾，那么我们可以得到S中的元素一定是最小元素d的倍数，也就是能被d整除。
|a|是属于S的，因为a>0，令x=1,y=0, a<0令x=-1,y=0。
同理|b|也属于S。我们题目里面a,b都是大于0的。
d是最小元素，且同时要整除a, b，那么d的范围只能只1 <= d <= gcd(a,b)
我们先得到1<=d<=gcd(a,b)这个结论，我们接下来继续确定d的取值。
d=ua+vb,从gcd(a,b)的定义来看d是能被gcd(a,b)整除的，因为ua能被gcd(a,b)整除，且vb也能
那么d>=gcd(a,b)
1) 1<=d<=gcd(a,b)
2) d >= gcd(a,b)
那么d = gcd(a,b)
所以我们得到S中最小元素d=gcd(a,b)
结合上面的结论得到S中所有元素都是gcd(a,b)的倍数。
所以我们只需要看 m 是否被 gcd(a,b)整除就知道xa + yb = m是否有解了。
代码很简单，就懒得贴了。
PS.不知道简书怎么打公式，所以上面证明的格式有点乱
