問題008
20億以下の正の整数a,bを入力したとき、aとbの最大公約数と最小公倍数を出力して終了するプログラムを作成してください。
ただし、aとbの最小公倍数は20億を超えないものとします。
入力
a(整数)
b(整数)
出力
最大公約数(整数)
最小公倍数(整数)
入力例
50000000
30000000
出力例
10000000
150000000
考え方
まず、最小公約数を求めます。
a,bの最小公約数は 1≦x≦(aとbで小さい方)です。
よって、aとbで小さい方から1まで調べていって、a,bを一番最初に両方割り切れたのが最大公約数です。
次に、最小公倍数ですが、素因数分解を使った次の例を見てください。
60と18の最大公約数
60と18の最小公倍数
最小公倍数の表をよく見てください。
全部かけあわせてしまうと、どうなるでしょうか。
最小公倍数と比べると、2と3が1つずつ余分ですね。
これは、最大公約数と一致しています。
よって、まずaとbをかけてしまって、余分な部分を最大公約数でわって排除すればOKです。
最小公倍数=a*b/最大公約数
注意
a,b,最小公倍数は20億以下ですが、a*bが20億以下とは限りません。
オーバーフローしないように気をつけましょう。
//
//A008.java
//
import java.io.*;
public class A008{
public static void main(String[] args)throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
//データ入力
int a=Integer.parseInt(br.readLine());
int b=Integer.parseInt(br.readLine());
//aとbで小さい方
int little=a>b?a:b;
//最大公約数を求める
//少ない方から1までiを変化させて、最初に両方が割りきれたのが最大公約数
//割り切れる=あまりが0(あまりは%で求められる)
int koyaku=0;
for(int i=little;i<=1;i++){
if(a%i==0 && b%i==0){
koyaku=i;
break;
}
}
//最小公倍数を求める
//a,bをかけて最大公約数で割ったのが最小公倍数
//かけたときオーバーフローするかもしれないのでlong型で計算
int kobai=(int)((long)a*b/koyaku);
//出力
System.out.println(koyaku);
System.out.println(kobai);
}
}
|
正しくゲームをするページ>パソコン甲子園攻略>ココ