問題

GCD and LCM

２０億以下の正の整数 a, b を入力したとき、a と b の最大公約数と最小公倍数を出力して終了するプログラムを作成して下さい。ただし、a と b の最小公倍数は 20 億を超えないものとします。

Input

複数のデータセットが与えられます。各データセットは１行に a と b が１つのスペースで区切られて与えられます。入力の最後まで処理して下さい。

Output

各データセットに対して、最大公約数と最小公倍数を１つのスペースで区切って１行に出力して下さい。

Sample Input

8 6
50000000 30000000

Output for the Sample Input

2 24
10000000 150000000

解法:ユークリッドの互除法

アルゴリズム

1. 入力を m, n (m ≧ n) とする。
2. n = 0 なら、 m を出力してアルゴリズムを終了する。
3. m を n で割った余りを新たに n とし、更に 元のnを新たにm とし 2. に戻る。

ユークリッドの互除法 (2011年9月16日 (金) 04:45)

#include <iostream>
using namespace std;

int main() {
   long long int a, b, t, aa, bb;

   while (1) {
      cin>>a;
      if (cin.eof()) break;
      cin>>b;

      aa = a;
      bb = b;

      while (1) {
         if (b==0) break;

         t = b;
         b = a % b;
         a = t;
      }
      cout<<a<<" "<<aa*bb/a<<endl;
   }
   return 0;
}

ツイート @nahcnujをフォロー Tweet to @nahcnuj