[Java] UVa 10193 All You Need Is Love

題目連結

題意:
有兩個數字S1, S2(以二進位表示)，如果存在一個數字 L (稱作"Love"，也是用二進位表示)，使得 S1 和 S2 一直減掉 L ，最後可以得到 L，就說 All you need is love! (他們都是由Love組成)，否則會輸出 Love is not all you need!。

仔細觀察可以發現，如果一個數N一直減掉某個數  L，最後還是得到 L，我們可以說 L 是 N 的因數。再者，題目有規定兩種限制，L 的開頭不會是0 (也就是一般二進位表示)，還不能只有一個位數(也就是最小為10表示的2)

所以整體來看，如果題目問的是只求S1是不是能只由Love組成，會變成求 S1 是不是質數(因數只有1跟自己，1又不符合 Love 定義)。今天是問同時滿足 S1 與 S2 的 L，也就是求 S1 與 S2 的公因數。如果找得到1以外的公因數，就輸出 All you need is love! ，否則稱為互質，輸出Love is not all you need!

解法:
首先要針對輸入的測資進行處理，測資是二進位表示的字串。在 Java 的 Integer 類別中，我們常見的 parseInt(String s) 可以把字串 s 轉成整數數值。其實這個 Method 有一個多載(Overloading)的形式 parseInt(String s, int radix)，radix表示前者字串的形式是幾進位。

如果我們寫 parseInt("111", 2)，就會得到 7 (回傳值是 int 型別)，parseInt("111", 10)就會得到111
。因此，輸入測資的二進位轉換可以在一行就結束。

接著，求公因數有一個直觀的做法，是對兩個數進行輾轉相除法。
(每次大扣小，如果扣到一邊為1，兩者互質；為0則表示有1以外的公因數)

如果寫 S1 - S2，但 S1 還是比 S2 大很多，會重複很多次，如果寫 S1%S2，就可以直接得到 S1 一直減 S2 到不能減之外，還跟你講剩下多少，此時這個結果會比 S2 小，因此在新的回合前，我們讓新的 S1 等於本來的 S2，新的 S2 等於剛剛的 % 結果，繼續進行。

假設一開始 S1 < S2 會發生什麼?
在 S1%S2 時，如果 S1 比較小，會回傳 S1 本身，新 S1 會去存 S2，新 S2 存 S1，等於只是做交換，以便下次正常執行。

觀察停止條件
在互質的情況，假設 S1=3, S2=1，下一次新 S1 會等於1，新 S2 = S1%S2 會是 0
有公因數的情況，假設 S1=4, S2=2，下一次新 S1=2( >1)，新 S2 = S1%S2 也是 0
所以 while 的條件是當 S2=0 跳出，此時比較 S1 是不是1即可。


程式(Java):