Snack [AtCoder Beginner Contest 148 C]

https://atcoder.jp/contests/abc148/tasks/abc148_c

前提知識

• 最小公倍数の効率的な求め方

解説

https://atcoder.jp/contests/abc148/submissions/9103143

今回の問題はAとBの最小公倍数が答えとなる。
ライブラリとして、最小公倍数を高速に求めるものをもっていれば、それを使うだけ。

最小公倍数を高速に求める方法を知らない方向けに少し説明をすると、
AとBの最小公倍数は、A*B/gcd(A,B)である。
gcd(A,B)はAとBの最大公約数のことである。
これには、ユークリッドの互除法という効率的な計算アルゴリズムがある。
これを使うと、O(log(A+B))くらいでGCDを求めることができる。
よって、これを持っていると答えることができる。

加えて、32bit整数ではオーバーフローする可能性があるので、注意。
C++ならlong longを使おう。

ll A, B;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B;
    cout << lcm(A, B) << endl;
}