問題
あるパン屋では、lo 個入りから hi 個入りまで、あらゆるサイズの箱にクッキーを詰めています。どのサイズの箱に詰めても余りが出ないような、1回分の焼き上げ数を決めたいと考えています。答えは lo から hi までのすべての整数で割り切れる最小の正の数、つまりそれらの最小公倍数です。
smallest_multiple(lo, hi) を実装してください。
入力
lo:最小の箱のサイズ。
hi:最大の箱のサイズ。
出力
lo, lo + 1, ..., hi のどれで割っても余りが出ない、最小の正の整数を返してください。
制約
1 ≤ lo ≤ hi ≤ 40(答えは符号付き64ビット整数に収まります)
例
入力:
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 です。
入力:
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用に調整されています。上記の説明と制約に従ってください。