８問目（最大公約数・最小公倍数）

問題

２０億以下の正の整数a,bを入力。最大公約数と、最小公倍数を出力。ただし、最小公倍数は２０億を超えない。

入力

a（整数）
b（整数）

出力

最大公約数（整数）
最小公倍数（整数）

入力例

500000000
300000000

出力例

100000000
1500000000

解き方例

典型的なアルゴリズム問題です。最大公約数（GCD）を求めるにはユークリッドの互除法をもちいます。

1. aをbで割ったあまりをcに代入する。
2. aにbを、bにcを代入する。
3. cが０でなければ１に戻る。
4. aが求める最大公約数になる。

引き算でする方法もありますが、こちらの方が数の差が大きいときの収束が早いです。でも、演算時間的には「div」は時間がかかりますけど（どうでも良いアセンブリネタでした）。

最小公倍数は、「どちらかを最大公約数で割ってもう一方と掛ける」と出ます。

ソースコード

お持ち帰り

C/C++

#include <stdio.h>

int GCD(int m,int n){
    if(n==0){
        return m;
    }else{
        return GCD(n,m%n);
    }
}


int main(){
    int m,n,gcd;

    scanf("%d\n%d",&m,&n);

    gcd= GCD(m,n);

    printf("%d\n%d",gcd,m/gcd*n);
    return 0;
}

その他

よくある問題です。「エラトステネスのふるい」なみによく出ます。覚えておきましょう。