すぐ解けそうだけど、ハマった。
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;
AC 取れました。
https://atcoder.jp/contests/math-and-algorithm/submissions/29166022
解説見ると、よりシンプルかつ効率が良いですね(除算が少ない)
なるほど。
LCM = (A / GCD(A, B)) * B;
コメント