アルゴリズムとデータ構造

減算を用いた最大公約数 (GCD)

与えられた2つの正の整数 a と b の最大公約数を求めます。ですが、今回は数値が非常に大きくなると想定されるため、両方の約数をすべて求めて共通の最大値を探す方法では間に合いません。より効率的なアルゴリズムに最適化する必要があります。
a > b の場合を考えてみましょう。共通の約数 d を考えると、a も b も d で割り切ることができます。つまり、
ここで x と y は整数です。もし a から b を引いた場合、次の計算になります:
 
つまり d は a と b の両方の約数であり、x と y が整数なら x-y も整数になります。したがって a-b も d で割り切れます。この事実を利用すると、計算ステップを効率的に減らすことが可能です。
最大公約数 d が a と b、そして a-b 全てを割り切るなら、「b と a-b の最大公約数」を求めることで、同じ d を見つけらるわけです。これを繰り返していき、どちらか一方が 0 になった場合、0 ではないほうの値が最大公約数となります。以下のプログラムを例に見てみましょう:
a, b = int(input()), int(input())
while a > 0 and b > 0:  # a または b が 0 の場合 => もう一方が GCD
    if b > a:           # a >= b を保つための処理
        a, b = b, a     # 2 つの値を入れ替える
    a, b = a - b, b     # (a, b) の gcd は (a, b - a) の gcd と同じ

d = b if a == 0 else a  # a が 0 => b が GCD, b が 0 => a が GCD
print('gcd:', d)
それでは、いくつか具体例を見ながらシミュレーションしてみましょう。
a = 8, b = 12
  1. b > a ⇒ swap ⇒ a = 12, b = 8
  1. b > a ⇒ swap ⇒ a = 8, b = 4
  1. a = 4 - 4 = 0, b = 4
  1. break ⇒ GCD = 4
a = 54, b = 24
  1. a = 54 - 24 = 30, b = 24
  1. a = 30 - 24 = 6, b = 24
  1. b > a ⇒ swap ⇒ a = 24, b = 6
  1. a = 18 - 6 = 12, b = 6
  1. a = 12 - 6 = 6, b = 6
  1. a = 6 - 6 = 0, b = 6
  1. break ⇒ GCD = 6
a = 17, b = 16
  1. a = 17 - 16 = 1, b = 16
  1. b > a ⇒ swap ⇒ a = 16, b = 1
  1. a = 14, b = 1
  1. a = 13, b = 1
  1. a = 12, b = 1
  1. …
  1. …
  1. a = 0, b = 1
  1. break ⇒ GCD = 1

Input

The only line of the input contains two integers a and b (0 ≤ a, b ≤ ).

Output

The program should print the greatest common divisor of a and b.

Examples

Input
Output
8 12
4
54 24
6
17 16
1

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue