最大公約数 (GCD)
与えられた正の整数
a と b について、これらの最大公約数 (greatest common divisor) を求めます。最大公約数とは、a と b の両方を割り切ることができる整数の中で、最も大きいものを指します。なお、任意の整数と 0 の最大公約数は、その整数自体となります。
入力
入力は 1 行のみで、整数
a と b (0 ≤ a, b ≤ ) が与えられます。出力
プログラムは、
a と b の最大公約数を出力してください。例
入力 | 出力 |
8 12 | 4 |
54 24 | 6 |
17 16 | 1 |
0 13 | 13 |
説明
- 8 は 1, 2, 4, 8 で、12 は 1, 2, 3, 4, 6, 12 ⇒ 最大の共通部分は 4
- 54 は 1, 2, 3, 6, 9, 18, 27, 54 で、24 は 1, 2, 3, 4, 6, 12, 24 ⇒ 最大の共通部分は 6
- 17 は 1, 17 で、16 は 1, 2, 4, 8, 16 ⇒ 最大の共通部分は 1
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB