裴蜀定理
对于整系数方程ax+by=m，设d =(a,b)
方程有整数解当且仅当d|m
这个定理实际上在之前学习拓展欧几里得解不定方程的时候就已经运用到
拓展到多元的方程一样适用
该方程有解当且仅当gcd(A1...AN)|s
要求s的值最小，那么答案就是gcd(A1..AN)
我们思考两个瓶子，设它们的容量为x,y，d=(x,y)
很容易看出不管怎么倒它们中的容量都是d的倍数
再思考两个容量互质的瓶子，设它们的容量为a,b
由于玩过某个CHL推荐的“高智商倒水游戏”...然后可以发现不论如何都可以倒到1
容量gcd为d的状态可以看做每滴水的重量为d，然后看做两个容量互质的瓶子，这样最后剩下d的水
猜想可以拓展到n的情况，也就是火星人倒的水应该是k个瓶子容量的最小公约数
然后就在n个数里挑k个数使得它们的最小公约数最大
把所有数的因子挑出来，从大到小一旦出现的次数超过k次就可以直接输出
看做可以做无限次的加减2a,2b(x和y中都可以)，和不超过1次的(x+a,y+b)(x+b,y+a)操作
为什么不是减？其实加减一样因为都可以通过前面的2a,2b操作得到
然后就可以直接裴蜀定理判定啦
END.
15 Apr.