[アルゴリズム x 数学] 問題3.2.3

すぐ解けそうだけど、ハマった。

1. 入力の積と GCD の積を保存しておいて、下記のように求める方法
最小公倍数 * 最大公約数(gcd_product) = A1 * A2 * … * An (=in_product)
最小公倍数 = in_product / gcd_product

案の定 WA。桁あふれが起きたのでしょうね・・・。
https://atcoder.jp/contests/math-and-algorithm/submissions/29147981

2. LCM で置き換えていく方法でも上手くいくのだと知り、実装
LCM = (A * B) / GCD(A, B);

これも WA。同じく桁あふれ。
https://atcoder.jp/contests/math-and-algorithm/submissions/29165938

3. じゃあこれなら溢れないだろ、再実装
gcd = GCD(A, B);
LCM = (A / gcd) * (B / gcd) * gcd;

解説見ると、よりシンプルかつ効率が良いですね(除算が少ない)
なるほど。

LCM = (A / GCD(A, B)) * B;