[程式] 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，這題就這樣而已。


實作如下：

	/*
	* =====================================================================================
	*
	* Filename: 946B.cpp
	*
	* Description: codeforces 946B: Weird Substraction Process
	*
	* Version: 1.0
	* Created: 2018/03/19 (yyyy/mm/dd)
	* Revision: none
	* Compiler: gcc
	*
	* Author: lionking
	* Organization: None
	*
	* =====================================================================================
	*/
	#include <stdio.h>
	int main()
	{
	long long int n, m;
	while (scanf("%lld %lld", &n, &m) == 2) {
	while ((n > 0) && (m > 0)) {
	if (n >= (m << 1)) { n %= (m << 1); }
	else if (m >= (n << 1)) { m %= (n << 1); }
	else { break; }
	}
	printf("%lld %lld\n", n, m);
	}
	return 0;
	}

view raw codeforces-946B.c hosted with ❤ by GitHub