LoginSignup
6
0

More than 3 years have passed since last update.

最小公倍数を求めるコードを書く時の注意点

Posted at

はじめに

以下のAtCoderの問題を解く際に、予め用意していた「最小公倍数を求める関数」を使ったのですが、オーバーフローが起きてしまいました。

C - Multiple Clocks

正の整数$a,b$について最小公倍数を$l$、最大公約数を$g$とすると、

ab = gl

となることが分かっています。このため、$\frac{ab}{g}$で最小公倍数を求めることができます。
ここで、$a*b$ を $g$ で割って最小公倍数を求めるような実装方法だと、上述したAtCoderの問題では$a*b$ のタイミングでオーバーフローが起こる可能性があります。
そのため、掛け算と割り算の順序を以下のように入れ替える必要があります。

コード(修正前)

int lcm(int x, int y) {
    return x * y / gcd(x, y);//この順番だとオーバーフローが起きやすい
}

コード(修正後)

int lcm(int x, int y) {
    return x / gcd(x, y) * y;//先に割り算をして掛けられる数を小さくして掛け算を行う
}

終わりに

ネットで調べてみると、修正前のパターンが紹介されていることが多かったため、私と同じような失敗をした方がいらっしゃるのではと思い当記事を書きました。
参考になれば幸いです。

6
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
6
0