最小公倍数 (LCM)
2 つの数
a と b の最小公倍数は、a と b の両方で割り切れる最小の数です。つまり、正の整数 x と y を使って かつ と表される数 l（最小公倍数）を求めることが目的です（2 ≤ x, y）。もっとも単純な方法として、
a の倍数（1·a, 2·a, 3·a, …）を順に調べ、その中で b でも割り切れる数字を探すというやり方が考えられます。しかし、この方法は非常に時間がかかる場合があります。たとえば、a と b が 13 と 17 のときには、1·13, 2·13, … を順番に確認し、ようやく 17·13 で両方割り切れることがわかるという具合です。実際のところ、
a·b は常に a と b の共通の倍数になりますが、必ずしもそれが最小とは限りません。たとえば、13 と 17 の場合はそれが最小でしたが、8 と 12 の場合はそうではありません。一般的には、a と b の最小公倍数は、a·b を gcd(a, b)（最大公約数）で割った値に等しくなります:この公式の直感的な理由としては、最小公倍数が「2 つの数のすべての共通の素因数を含む最小の倍数」であることが挙げられます。そして、2 つの数の最大公約数は「共通する素因数の積」なので、
a·b に含まれる重複した素因数を gcd(a, b) で除いてあげれば、ちょうど両方の数に含まれる最大の素因数の冪だけを持つ倍数、すなわち最小公倍数が得られます。したがって、2 つの数の最小公倍数を求めるには、まずそれぞれの数を素因数分解し、各素数について両方の数に現れる最大の指数を取って掛け合わせればよいことになります。
ここで
a·b は a と b の両方の素因数を指数を足し合わせた形で含みます。一方で gcd(a, b) は共通している素因数の最小の指数を持っているので、それを分母に据えることで冗長な因数分を取り除くことになり、ちょうど最小公倍数が得られる仕組みです。入力
1 行目に、2 つの整数
a と b (1 ≤ a, b ≤ ) が与えられます。出力
a と b の最小公倍数を出力してください。例
入力 | 出力 |
8 12 | 24 |
54 24 | 216 |
17 16 | 272 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB