😄

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

2021/04/22に公開

1.概要

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

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()

4.計算量改善

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

5.終わりに

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

Discussion