kouhouyoukai さんの問題

Twitter に挙がっていた問題は以下の通り

a, b, m はいずれも正の整数、かつ a > b のときに、a ÷ b × m の結果が整数となる最小の m の求め方

例としては a = 1440, b = 70 であった場合は、m = 7 が求められるみたいな感じのをやりたい 回答は数学的記述、JS 等のコードどちらでもおｋです

解いてみた

賢明な諸君であればこれが LCM を使って簡単に解けることは想像がつくと思う。a, bの大小関係の条件については等しくなければ与えられた二つの数の大きい方をaにすればいいだけなので結局入力としてはどちらが大きくても良い。

a ÷ b × m の結果が整数となる最小の m の求め方

除算の結果が整数になるということは、割り切れるということなので自然数 a, b と互いに素な自然数 m, n を用いて、

m, n は互いに素

最初に記事を書いた時、この条件をつけるのをすっかり忘れていました。

この問題は解が無限にあるのですが、互いに素という条件をつけることで最小の唯一の解を得ることができます。

$a/b*m=n$

の条件を満たせば良いということになる。これを式変形すれば、

$a*m=b*n$

が得られる。これは要するに最小公倍数を求めろという問題になる。

最小公倍数を求めるには素因数分解などを用いるものなどが考えられるが、もっと便利な方法として GCD を利用する方法がある。

二つの正の整数においては、

$GCD(a,b)*LCM(a,b)=ab$

が成立するので、これを式変形して、

$LCM(a,b)=ab/GCD(a,b)$

を得る。

ここで、問題の条件に戻ると

$LCM(a,b)=a*m=b*n$

と表されるはずなので、m を求めたければ、

$LCM(a,b)=a*m$

を利用すればよい。

これを代入すると、

$a*m=ab/GCD(a,b)$

となり、両辺を$a!=0$で除すれば、

$m=b/GCD(a,b)$

が得られる。

よって、求めたい$m$は$b$を$a$と$b$の最大公約数で割ったものに等しいということになる。

アルゴリズム

GCD を求めるにはユークリッドの互除法 (opens new window)を使うのが恐らく最も高速である。

これが 2000 年以上も前に考えられたというのは本当に驚くべきことである。

func gcd(_ a: Int, _ b: Int) -> Int {
    a % b == 0 ? b : gcd(b, a % b)
}

Swift で記述すると上のようなコードになる。たった一行で書ける簡潔なアルゴリズムである。

再帰処理をしているのであまり速くないかもしれないが、計算量も知れているのでほとんど差はないと言ってよいだろう。

これは GCD を求めるだけなので、kouhouyoukai さんが欲しい$m$を求めるコードは、

func gcd(_ a: Int, _ b: Int) -> Int {
    a % b == 0 ? b : gcd(b, a % b)
}

func kouhouyoukai(_ a: Int, _ b: Int) -> Int {
    return b / gcd(a, b)
}

print(kouhouyoukai(1440, 70)) // Output 7

となり、実行すると確かに 7 が得られるのがわかる。

記事は以上。