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

1 min read読了の目安(約1700字 1

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.終わりに

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