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

GCD - Euclid’s algorithm

アルゴリズムを数回反復すると、いくつかの重複した処理があることに気づき、実は最大公約数 (GCD) を求めるアルゴリズムはさらに最適化できることがわかります。
減算を使う方法では、大きい数から小さい数を引き続けて、結果が 0 または GCD と等しい数になるまで処理を進めます。これをより効率的に行うために、大きい数を小さい数で割った余りを使います。つまり、割り算の余り (modulo) を求めながら、大きい数を小さい数で何度も割っていき、余りが 0 になるまで繰り返します。最後に得られる 0 でない余りが GCD になります。
modulo 演算を使うやり方は、GCD を求めるうえでより効率的だと考えてください。小さい数を大きい数から繰り返し減算する代わりに、割り算を用いて大きい数を一気に小さくできます。両方の数を共通の約数で徐々に割っていくイメージなので、最大公約数にずっと早く到達します。
a, b = int(input()), int(input())
while a > 0 and b > 0:  # aまたはbが0の場合 ⇒ もう一方がGCD
    a, b = b, a % b     # (a, b) のgcdは (b, a % b) のgcdと同じ

d = b if a == 0 else a  # aが0ならbがGCD、bが0ならaがGCD
print('gcd:', d)
このアルゴリズムは、紀元前 300 年に書かれたユークリッドの著書で最初に言及されています。
 
いくつかアルゴリズムのシミュレーションを見てみましょう:
a = 8, b = 12
  1. a = 12, b = 8
  1. a = 8, b = 4
  1. a = 4, b = 0
  1. break ⇒ GCD = 4
a = 54, b = 24
  1. a = 24, b = 6
  1. a = 6, b = 0
  1. break ⇒ GCD = 6
a = 17, b = 16
  1. a = 16, b = 1
  1. a = 1, b = 0
  1. break ⇒ GCD = 1

入力

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

出力

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

例

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