经典问题

倒水问题解析

　　有两个容器，容积分别为A升和B升，有无限多的水，现在需要C升水。 我们还有一个足够大的水缸，足够容纳C升水。起初它是空的，我们只能往水缸里倒入水，而不能倒出。 可以进行的操作是： 把一个容器灌满； 把一个容器清空（容器里剩余的水全部倒掉，或者倒入水缸）； 用一个容器的水倒入另外一个容器，直到倒出水的容器空或者倒入水的容器满。     问是否能够通过有限次操作，使得水缸最后恰好有C升水。

输入：三个整数A, B, C，其中 0 < A , B, C B，那么每次可以倒的水的量为A , B , (A + B) ,( A - B)升水，设置4个因子，分别为x1 ,  x2,  x3,  x4 , (x1 , x2, x3, x4 属于整数)，如果可以使得水缸最后恰好有C升水，那么必然存在整数x1 , x2, x3, x4，使得

　　　　　　　　　　Ax1 + Bx2, +  (A + B)x3  + (A - B)x4  = C    等式成立;

　　对等式做一定的变换，得到公式

　　　　　　　　　　(x1 + x3 + x4)A + (x2 + x3 - x4)B = C ;     --( 1-1 )

　　设 x = x1 + x3 + x4 , y = x2 + x3 - x4 ,  x, y 均为整数;最终得到公式

　　　　　　　　　　xA + yB = C ;                                         --( 1-2 )       

　　 x1 ,  x2,  x3,  x4可以假设为正整数，用几个for循环可以实现，但是时间复杂度太大，为O(N4)，题目中给的范围是0 < A , B, C