Getting Started - Greatest Common Divisor

時間制限 : 1 sec, メモリ制限 : 65536 KB
英語版はこちら

最大公約数

2つの自然数 x, y を入力とし、それらの最大公約数を求めるプログラムを作成してください。

2つの整数 xy について、x ÷ dy ÷ d の余りがともに 0 となる d のうち最大のものを、xy の最大公約数(Greatest Common Divisor)と言います。例えば、35 と14 の最大公約数 gcd (35, 14) は 7 となります。これは、35 の約数{1, 5, 7, 35}、14 の約数 {1, 2, 7, 14} の公約数 {1, 7} の最大値となります。

入力

xy が1つの空白区切りで1行に与えられます。

出力

最大公約数を1行に出力してください。

制約

  • 1 ≤ x, y ≤ 109

ヒント

整数 x, y について、xy ならば xy の最大公約数は yx % y の最大公約数に等しい。ここで x % yxy で割った余りである。 

入力例 1

147 105

入力例 1 に対する出力

21

Note

      解説