uva571专题

uva571 - Jugs(水壶)

贴出以为大神的分析。。。。简明易懂 本题只要求给出一个解,不要求最优。所给的两个罐子容量一定互质,因此必然可以倒出从0到大罐容量间的任何整数值。原理是若A,B互质,则最小公倍数为A×B,即不存在一个1 < n < B,使得nA能被B整除。令r = nA mod B(mod为取模操作),那么当n从0到B-1变化时,r可以取到0到B-1之间的任何值。这个是很容易证明的,但我的证明过程非常不专业,