けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 148 C - Snack (300 点)

結構、そのまんまな問題が来ましたね。

問題へのリンク

問題概要

2 つの正の整数  A, B が与えられる。
 A でも  B でも割り切れる正の整数のうち、最小の値を求めよ。

制約

  •  1 \le A, B \le 10^{5}

考えたこと

すごくそのまんまですね。 A B最小公倍数を求めよ、という問題。実は  A B の最大公約数を  G、最小公倍数を  L とすると

  •  A \times B = G \times L

が成立します。たとえば、 4 6 の最大公約数は 2、最小公倍数は 12 ですが、

  •  4 \times 6 = 24
  •  2 \times 12 = 24

となっています。つまり、この問題は

  •  A B の最大公約数を求める ( G とする)
  •  \frac{A \times B}{G} を答える

とすればよいです。多少の工夫点として、計算する順番は

A * B / G

とするのではなく、

A / G * B

とすると、オーバーフローのリスクが少し減ります。 G A の約数なので、 A / G は必ず割り切れます。

#include <iostream>
using namespace std;

long long GCD(long long x, long long y) {
    return (y ? GCD(y, x%y) : x);
}

int main() {
    long long A, B;
    cin >> A >> B;
    long long G = GCD(A, B);
    cout << A/G * B << endl;
}