# 大雄的最大公因數
https://neoj.sprout.tw/problem/346/
就讀於野比高中裡的學生大雄，最喜歡找最大公因數(GCD)了！一天因緣際會，大雄學會了一種神秘演算法，可以快速找出GCD。

首先給定a, b兩個數字，要快速找出兩數GCD的方法為：

1. 若有其中一數為零，那答案就是另一個不為零的數字

2. 如果兩數都是偶數，那麼答案就是「2×(這兩個數字都除以二之後，再丟進這個演法裡計算出的值)」

3. 如果兩數都是奇數，假設兩數一大一小，答案是 (大數 − 小數) 和 小數 ，這兩個新數字再丟進演算法裡計算出的值

4. 如果兩數為一偶一奇，那麼答案就是把偶數除以二，另一數不變，再度丟進這個演算法裡算

如果真的聽不懂的話，可以參考這裡的說明

### 輸入說明
第一行有兩個數字 a, b ，請求出 a, b 的最大公因數
+ $1≤a≤10^9$
+ $1≤b≤10^9$
(在 int 可以存的範圍內)

### 輸出說明
輸出每一步驟做的內容並換行，最後一行輸出最大公因數

步驟說明：

+ 其中一數為零輸出 one zero
+ 兩數都是偶數輸出 both even
+ 兩數都是奇數輸出 both odd
+ 兩數一偶一奇輸出 one odd
### 範例輸入

4 2

### 範例輸出

both even
one odd
both odd
one zero
2

# Code

#include <iostream>
using namespace std;

int Gcd(int a, int b)
{
  if (a == 0 || b == 0)
  {
    cout << "one zero\n";
    return a + b;
  }
  if (a % 2 == 0 && b % 2 == 0)
  {
    cout << "both even\n";
    return 2 * Gcd(a / 2, b / 2);
  }
  if (a % 2 != 0 && b % 2 != 0)
  {
    if (a > b)
      a -= b;
    else
      b -= a;
    cout << "both odd\n";
    return Gcd(a, b);
  }
  if (a % 2 == 0)
    a /= 2;
  if (b % 2 == 0)
    b /= 2;
  cout << "one odd\n";
  return Gcd(a, b);
}

int main()
{
  int a, b;
  cin >> a >> b;
  int c = Gcd(a, b);
  cout << c << "\n";
}