kouhouyoukai さんの問題#

解いてみた#

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

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

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

:::tip 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$の最大公約数で割ったものに等しいということになる。

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

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