AOJ 0005 （GCD and LCM : 最大公約数と最小公倍数）
【問題】
https://onlinejudge.u-aizu.ac.jp/problems/0005
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0005
【解説】
整数\(a,b\)の最大公約数と最小公倍数を求める問題。最小公倍数は最大公約数が求まれば簡単に求まるため、まずは最大公約数を求める。
最大公約数はユークリッドの互除法にて求めていけばよい。
競技プログラミングでは、最大公約数を求めるシーンが多いため、これはライブラリ化して持っておくと便利である。
後は、を最大公約数で割れば、最小公倍数が求まる。（正の整数
に対して，それらの最大公約数を
，最小公倍数を
とおくと
となるため。）
【コード】
