OJ题目：click here~~ 题目分析：九度上这道没有要求最少步数，只要得到最后结果即可AC ， bfs ， dfs都行。最少步骤的方法肯定也能AC啦，分析如下。 输入的三个数：a,b,n;> 由题不定方程ax+by=n必定有解> 如果b=n，则fill B即可，否则用试探法求出这样的两组解（a1，b1）及（a2，b2），其中a1 >0，b1<0；a1是满足方程的最小正整数；a2

原题： In the movie “Die Hard 3”, Bruce Willis and Samuel L. Jackson were confronted with the following puzzle. They were given a 3-gallon jug and a 5-gallon jug and were asked to fill the 5-gallon jug

原题大意： 　　　　你有两个杯子，A、B；你只有三种操作，（1）清空任何一个杯子 （2）当被子是空的时候可以填满任何一个杯子  （3）将某一杯的水倒到另一杯中（不会溢出计算）直到B杯达到目标数Aim C。 　　　　输入的A、B升数有要求，一定需要相邻互质。并且A小于B，且目标数Aim C要小于B即可。 　　　　题目好像想象挺容易，手写也好像能解出来，但就是电脑老是犯傻逼。扔HDU的OJ上老是

原题大意： 　　　　你有两个杯子，A、B；你只有三种操作，（1）清空任何一个杯子 （2）当被子是空的时候可以填满任何一个杯子  （3）将某一杯的水倒到另一杯中（不会溢出计算）直到B杯达到目标数Aim C。 　　　　输入的A、B升数有要求，一定需要相邻互质。并且A小于B，且目标数Aim C要小于B即可。 　　　　题目好像想象挺容易，手写也好像能解出来，但就是电脑老是犯傻逼。扔HDU的OJ上老是

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

参考：https://www.cnblogs.com/devymex/archive/2010/08/04/1792288.html Time limit: 3.000 seconds  Background In the movie "Die Hard 3", Bruce Willis and Samuel L. Jackson were confronted with the