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; }