簡単 0件解決済み 正答率0%

範囲の最小公倍数

ある範囲のすべての整数で割り切れる、最小の正の数を求めます。

このチャレンジで学べること

  • gcd(a, b) から lcm(a, b) を求められる
  • 範囲内の数に対して演算を順に畳み込める
  • 途中の値をオーバーフローさせないようにできる

問題

原文(英語)を表示

あるパン屋では、lo 個入りから hi 個入りまで、あらゆるサイズの箱にクッキーを詰めています。どのサイズの箱に詰めても余りが出ないような、1回分の焼き上げ数を決めたいと考えています。答えは lo から hi までのすべての整数で割り切れる最小の正の数、つまりそれらの最小公倍数です。

smallest_multiple(lo, hi) を実装してください。

入力

lo:最小の箱のサイズ。

hi:最大の箱のサイズ。

出力

lo, lo + 1, ..., hi のどれで割っても余りが出ない、最小の正の整数を返してください。

制約

1 ≤ lo ≤ hi ≤ 40(答えは符号付き64ビット整数に収まります)

例

例 1
入力:
lo = 1
hi = 6

期待される出力:
expected = 60
入力:
long long lo = 1;
long long hi = 6;

期待される出力:
long long expected = 60;
入力:
long lo = 1;
long hi = 6;

期待される出力:
long expected = 60;

解説

60 は 1, 2, 3, 4, 5, 6 のすべてで割り切れ、それより小さい正の数ではそうならないので、答えは 60 です。

例 2
入力:
lo = 4
hi = 6

期待される出力:
expected = 60
入力:
long long lo = 4;
long long hi = 6;

期待される出力:
long long expected = 60;
入力:
long lo = 4;
long hi = 6;

期待される出力:
long expected = 60;

解説

lcm(4, 5) = 20、lcm(20, 6) = 60 なので、答えはやはり 60 です。小さいサイズは結果に影響しません。

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

範囲全体の最小公倍数は、1つずつ数を加えながら求められます。

ヒント 2

lcm(a, b) = a / gcd(a, b) × b です。

ヒント 3

先に割ってから掛ければ、途中の値が答えより大きくなることはありません。

目安の計算量

時間 O(n log M)、追加メモリ O(1)

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。