問題112：正の整数 $a, b$ ($a < b$) について、最大公約数が30で、最小公倍数が1800であるような $a, b$ の組が何組あるかを求める問題です。 問題113： (1) 30! が $2^m$ で割り切れるとき、最大の $m$ の値を求める問題です。 (2) 125! は末尾に0が連続して何個並ぶかを求め、それを利用して $n!$ が $10^{40}$ で割り切れる最小の $n$ の値を求める問題です。

1. 問題の内容

問題112：正の整数 $a, b$ ($a < b$) について、最大公約数が30で、最小公倍数が1800であるような $a, b$ の組が何組あるかを求める問題です。

問題113：

(1) 30! が $2^m$ で割り切れるとき、最大の $m$ の値を求める問題です。

(2) 125! は末尾に0が連続して何個並ぶかを求め、それを利用して $n!$ が $10^{40}$ で割り切れる最小の $n$ の値を求める問題です。

2. 解き方の手順

問題112：

$a$ と $b$ の最大公約数が30なので、$a = 30x$, $b = 30y$ と表せる。ここで、$x$ と $y$ は互いに素な正の整数で、$x < y$ である。

最小公倍数が1800なので、 $30xy = 1800$ となる。

よって、$xy = 60$ である。

$x$ と $y$ は互いに素なので、$x$ と $y$ の組み合わせは以下の通りである。

(1, 60), (3, 20), (4, 15), (5, 12)

これらの組み合わせに対応する $a$ と $b$ は、それぞれ

(30, 1800), (90, 600), (120, 450), (150, 360)

よって、$a, b$ の組は4組ある。

問題113：

(1) 30! が $2^m$ で割り切れるとき、最大の $m$ の値を求める。

$m = \lfloor\frac{30}{2}\rfloor + \lfloor\frac{30}{4}\rfloor + \lfloor\frac{30}{8}\rfloor + \lfloor\frac{30}{16}\rfloor = 15 + 7 + 3 + 1 = 26$

よって、最大の $m$ の値は26である。

(2) 125! は末尾に0が連続して何個並ぶかを求める。

125! が $10^k$ で割り切れる最大の $k$ を求める。これは125!に含まれる5の因子の個数を数えればよい。

$k = \lfloor\frac{125}{5}\rfloor + \lfloor\frac{125}{25}\rfloor + \lfloor\frac{125}{125}\rfloor = 25 + 5 + 1 = 31$

よって、125!は末尾に0が31個連続して並ぶ。

$n!$ が $10^{40}$ で割り切れる最小の $n$ の値を求める。つまり、$n!$ に含まれる5の因子の個数が40以上になる最小の $n$ を求める。

$f(n) = \lfloor\frac{n}{5}\rfloor + \lfloor\frac{n}{25}\rfloor + \lfloor\frac{n}{125}\rfloor + ...$

$f(150) = 30 + 6 + 1 = 37$

$f(160) = 32 + 6 + 1 = 39$

$f(165) = 33 + 6 + 1 = 40$

よって、$n!$ が $10^{40}$ で割り切れる最小の $n$ の値は165である。

3. 最終的な答え

問題112：4組

問題113：

(1) 26

(2) 31, 165