TOYPRO解説記事 - 最小公倍数(200点)

1.概要

問題はコチラ！(https://app.toy-pro.net/user/questions/190)

この問題は、最小公倍数をモチーフとした問題です。
なるべくわかりやすい記事を心がけていますが、最小公倍数を学校で履修する小学5年生よりも下の学年の方は、理解するのが難しいかもしれません。
しかし、頑張って理解することが、プログラミングだけでなく、学校での数学の先取りとなり、より深い理解につながると思いますので、是非チャレンジしてみてください。

2.問題

太郎くんは、整数$k$の倍数が大好きです。
花子ちゃんは、整数$n$の倍数が大好きです。
太郎くんと花子ちゃん、両方が好きでいちばん小さい数を求めてください。

制約

$1 ≦ k, n ≦ 100$

入力例

k = 7
n = 3

出力例

21

3.解説

3-1.問題の考察

太郎くんは、整数$k$の倍数が大好きです。
花子ちゃんは、整数$n$の倍数が大好きです。
太郎くんと花子ちゃん、両方が好きでいちばん小さい数を求めてください。

とのことなので、整数$k$, 整数$n$の最小公倍数を求めればよいです。
最小公倍数とは、

$0$ではない複数の整数の公倍数のうち最小の自然数をさす。
(出典:https://ja.wikipedia.org/wiki/最小公倍数)

という意味です。この問題は最小公倍数を求める問題そのものですね!

3-2.どうやって求めればいいの?

とはいえ、最小公倍数をどう求めるかは、かなり難しい問題です。
しかしながら、この問題の制約はそんなに厳しくなく、全探索をすることで実装できます。
なぜなら、公倍数が最低1つある範囲があまり広くないからです。
では、「公倍数が最低1つある範囲」を求めてみましょう。

整数$a, b$があります。
このとき、絶対に公倍数になる数は$a × b$です。
これは考えてみたらわかるでしょう。
では、この問題の制約の中で、$a × b$が最大の場合は、どんな数になるでしょうか。

そうですね、当たり前ですが$100 × 100$です。
$100 × 100 = 10000$なので、この問題の制約下で最大でも$10000$の範囲に最小公倍数が存在することがわかりました。

3-3.どういうコードになるの?

全探索をすればいいだけなので、簡単なforで実装できます。

k = 7
n = 3

for i in range(1, 10000 + 1):
    if i % k == 0 and i % n == 0:
        print(i)
        exit()

range(1, 10000 + 1)としているのは、$range(a, b)$が$a$以上$b - 1$以下の整数を返すからです。

4.計算量改善

先程の実装では、$O(10^4)$かかります。これでも勿論十分なのですが、ユークリッドの互除法というアルゴリズムを使い、最大公約数を求めたあと、最小公倍数を求めることでこれより何倍も高速に解を出す事ができます。
また、ToyProでは対応していませんが、Python3.9以上のバージョンでは、lcm()という最小公倍数を求める関数がmathライブラリに搭載されていますので、この問題以外でも最小公倍数を使う機会があったら試してみると良いでしょう。

5.終わりに

今回の問題は、一見全探索できない(というかどういうふうにすればよいのかわかりにくい)ですが、制約を見ることで解法を思いつくことができました。
このように、制約がかなり深く関係してくる問題がよくあるので、しっかり見るようにしましょう。