題目如下：
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 with exactly 4 gallons. This problem generalizes that puzzle.
You have two jugs, A and B, and an infinite supply of water. There are three types of actions that you can use: (1) you can fill a jug, (2) you can empty a jug, and (3) you can pour from one jug to the other. Pouring from one jug to the other stops when the first jug is empty or the second jug is full, whichever comes first. For example, if A has 5 gallons and B has 6 gallons and a capacity of 8, then pouring from A to B leaves B full and 3 gallons in A.
A problem is given by a triple (Ca,Cb,N), where Ca and Cb are the capacities of the jugs A and B, respectively, and N is the goal. A solution is a sequence of steps that leaves exactly N gallons in jug B. The possible steps are
fill A
fill B
empty A
empty B
pour A B
pour B A
success
where "pour A B" means "pour the contents of jug A into jug B", and "success" means that the goal has been accomplished.
You may assume that the input you are given does have a solution.
Input
Input to your program consists of a series of input lines each defining one puzzle. Input for each puzzle is a single line of three positive integers: Ca, Cb, and N. Ca and Cb are the capacities of jugs A and B, and N is the goal. You can assume 0 < Ca <= Cb and N <= Cb <=1000 and that A and B are relatively prime to one another.
Output
Output from your program will consist of a series of instructions from the list of the potential output lines which will result in either of the jugs containing exactly N gallons of water. The last line of output for each puzzle should be the line "success". Output lines start in column 1 and there should be no empty lines nor any trailing spaces.
Sample Input
3 5 4
5 7 3
Sample Output
fill B
pour B A
empty A
pour B A
fill B
pour B A
success
fill A
pour A B
fill A
pour A B
empty B
pour A B
success
簡單來說就是我們以前做的智力題，有兩個容積為a、b的罐子，要倒出c升水來，題目假設(shè)了a，b互素并且a<b,c<b.
根據(jù)歐拉定理：
若n,a為正整數(shù)，且n,a互質(zhì)，則（其中φ(n)為歐拉函數(shù)）:a^(φ(n))同余1（mod n）
題目中a，b互質(zhì)，如此一來也就是存在正整數(shù)k=a^(φ(b)-1)，使得k*a mod b=1.
這樣只需要從a向b倒水，b滿了就倒空，最終能夠得到1升水，將這個行為重復(fù)c次就能得到c升水。
以上只是說明了可行性，事實上在實際操作很容易發(fā)現(xiàn)并不需要那么多次的操作，例如，7 和 5，根據(jù)歐拉定理，（7^4）*7 mod 5=1，不過稍加計算就發(fā)現(xiàn)7*3 mod 5=1，所以只需要三次操作就得到了1升水。
在代數(shù)學(xué)有一個定理，對任意兩個多項式f(x)和g(x),若他們最大公因式為d(x),那么d可以表示為f 、g的一個組合，即：
存在多項式u，v使得d=uf+vg
代數(shù)里面多項式是對整數(shù)更高層的推廣，以上定理中的多項式可以完全改為整數(shù)。
顯然1是a，b的最大公因式,那么存在整數(shù)e，f，使得1=ea+fb.
e和f至少一個是負(fù)數(shù)，如果e是負(fù)數(shù)，那么只需要從a向b倒水，b滿了就倒空，最終能夠得到1升水。
不過此處有個小問題，并不能解釋為什么我們從小罐子向大罐子倒水總能獲得成功。
需要進(jìn)一步證明，已知b>a，如果e<0,f>0;由1=ea+fb,可以推知1=(e+kb)a+(f-ka)b,取一個充分大的k就能使得e+kb>0,(f-ka)<0.得證
以上兩種方法都只是從某些側(cè)面看待問題，得到的結(jié)論不是問題的本質(zhì)，我們會發(fā)現(xiàn)用ka 去mod b，當(dāng)k從0開始取到b-1，得到的模數(shù)會包含a，b最大公因數(shù)的所有倍數(shù) mod b。這顯然不是巧合，可以用python簡單驗證一下：
for i in range(12):{print((i*9)%12)}
輸出：
0
{None}
9
{None}
6
{None}
3
{None}
0
{None}
9
{None}
6
{None}
3
{None}
0
{None}
9
{None}
6
{None}
3
{None}
可以看出包含了0,3,6,9
這一點(diǎn)可以從以下歐幾里得算法看出來
