$n! = n \times (n-1)!$ より、 $m \leq n$ です。
また、この問題には単調性があります。すなわち、ある整数 $u$ に対して $u!$ が $n$ で割り切れるなら $u$ 以上の数 $v$ に対して $v!$ は $u!$ の倍数なので $n$ で割り切れます。よって、二分探索を用いることで $m!$ が $n$ で割り切れるかを判定する問題を $O(\log n)$ 回解けば正解することができます。この判定問題を考えましょう。

$n$ を素因数分解した場合、 $a_1^{b_1} \times a_2^{b_2} \times \cdots \times a_z^{b_z}$ と表せるとします。
このとき、 $m$ の階乗が $n$ で割り切れる必要十分条件は「 $m!$ の $a_i$ の指数が $b_i$ 以上であることが $1 \leq i \leq z$ について成り立つ」です。

$m!$ の $a_i$ の指数はどう計算すればいいでしょうか。実は、 $m!$ が素数 $p$ で割り切れる回数は $\lfloor \frac{m}{p} \rfloor + \lfloor \frac{m}{p^2} \rfloor + \cdots + \lfloor \frac{m}{p^m} \rfloor$ と一致するという性質があります。これを計算するとき、 $p^q > m$ となる $q$ 以上の整数 $r$ について $\lfloor \frac{m}{p^r} \rfloor = 0$ が成り立つので、実際にはこの計算は $O(\log m)$ 回で打ち切ることができます。

よって、 $m!$ の $a_i$ の指数は $O(\log m)$ で求められるので、 $m!$ が $n$ で割り切れるかの判定は $O(z \log m)$ で可能です。

また、 \(n\) の素因数分解は \(O(\sqrt{n})\) でできるので、この問題は \(O(\sqrt{n}+z (\log n )^2)\) で解くことができました。
本問題の制約において \(z \leq 9\) なので、これは十分高速です。