2018年3月19日

[程式] codeforces 946B: Weird Subtraction Process

[題意] 給 2 個數字 n, m (1 <= n, m <= 10^18),問經過下列操作後 n 跟 m 的值為何?
  1. 若 n >= 2*m,則 n = n - 2*m,並回到步驟 1。
  2. 若 m >= 2*n,則 m = m - 2*n,並回到步驟 1。
  3. 若 n 或 m 其中一個為 0,或是上述二個條件均失敗時,結束。

舉例來說:n = 12, m = 5。
  1. 因為 n >= 2*m,所以 n = 12 - 2*5 = 2。此時 n = 2, m = 5。
  2. 因為 m >= 2*n,所以 m = 5 - 2*2 = 1。此時 n = 2, m = 1。
  3. 因為 n >= 2*m,所以 n = 2 - 2*1 = 0。此時 n = 0, m = 1。
  4. 因為 n 為 0,結束。
因此最後結果 n = 0, m = 1

另一個例子是 n = 31, m = 12。
  1. 因為 n >= 2*m,所以 n = 31 - 2*12 = 7。此時 n = 7, m = 12。
  2. 因為 n < 2*m 且 m < 2*n,所以直接結束。
因此這個例子的答案是 n = 7, m = 12

[解法] 其實有點像是輾轉相除法找最大公因數,不過小改一點點,唯一的小麻煩就是像第二個例子那樣,雖然還沒找到最大公因數,但是因為已經觸發條件了所以就終止計算了。但也不能傻傻地用暴力法硬算,因為 n 跟 m 的值很大,所以如果兩者差距很大還直接一步一步慢慢算會很慢,所以要稍稍修改一下輾轉相除法的概念。

其實如果有透徹了解輾轉相除法的話,只要改成這樣就好:
  1. 若 n >= 2*m,則 n = n mod 2*m
  2. 若 m >= 2*n,則 m =m mod 2*n
另一方面,因為數值很大,所以要用 long long int 來存 n 跟 m,這題就這樣而已。


實作如下:

沒有留言:

張貼留言