AIZU ONLINE JUDGE http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0005&lang=jp
GCD and LCM
２０億以下の正の整数 a, b を入力したとき、
a と b の最大公約数と最小公倍数を出力して終了するプログラムを作成して下さい。
ただし、a と b の最小公倍数は 20 億を超えないものとします。
Input
複数のデータセットが与えられます。
各データセットは１行に a と b が１つのスペースで区切られて与えられます。
入力の最後まで処理して下さい。
Output
各データセットに対して、最大公約数と最小公倍数を１つのスペースで区切って１行に出力して下さい。
回答：AOJ/vol0/AOJ0005.cpp at master · wada811/AOJ · GitHubGCD( greatest common divisor:最大公約数)最大公約数 - Wikipedia
LCM( least common multiple:最小公倍数)最小公倍数 - Wikipedia
ユークリッドの互除法 - Wikipedia
基礎知識としては以上の3つ。
GCDをユークリッドの互除法で求めて、LCM = a * b / GCD でLCMを求める。
ユークリッドの互除法のアルゴリズムはこちら↓が参考になった。
最大公約数を求める2つのアルゴリズムを書いてみた - sh-2の日記
他にもGCDを求める方法はあるみたいだけどわかりやすさでユークリッドの互除法が一番かな。
20億とか言われて面食らった。データ型の最大値を覚えていないので調べると long で大丈夫らしい。
Ｃ言語講座：色々なデータ型の最大値、最小値
LCMを求める時に上の式で計算すると一時的に long の最大値すら超えるので先にGCDで割る必要がある。
それではまた明日。
