問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$N!$ が $K$ の倍数であるような最小の正の整数 $N$ を求めよ.

制約

$2 \leq K \leq 10^{12}$

解法

正の整数 $n$ と素数 $p$ に対して, $\nu_p(n)$ で $n$ を割り切る $p$ の最大回数とする.

このとき, 整数 $n,m$ と素数 $p$ に対して, $\nu_p(nm)=\nu_p(n)+\nu_p(m)$ が成り立つことから,

$\displaystyle \nu_p(N!)=\sum_{n=1}^N \nu_p(n)$

が成り立つ.

そして, 右辺について, 正の整数 $k$ に対して, $\displaystyle k=\sum_{i=1}^\infty [i\leq k ]$ が成り立つことから,

$\displaystyle \sum_{n=1}^N \nu_p(n)=\sum_{n=1}^N \sum_{i=1}^\infty [i \leq \nu_p(n) ]=\sum_{i=1}^\infty \sum_{n=1}^N [i \leq \nu_p(n) ]$

となる *1.

ここで, $i \leq \nu_p(n)$ であることと, $n$ が $p^i$ の倍数であることは同値である. $1$ 以上 $N$ 以下の整数のうち, $p^i$ の倍数であるような整数は $\left \lfloor \dfrac{N}{p^i} \right \rfloor$ 個である. よって,

$\displaystyle \nu_p(N!)=\sum_{i=1}^\infty \sum_{n=1}^N [i \leq \nu_p(n) ]=\sum_{i=1}^\infty \left \lfloor \dfrac{N}{p^i} \right \rfloor$

である.

また, 正の整数 $n,m$ に対して, $n$ が $m$ の倍数であることの必要十分条件は, 任意の素数 $p$ に対して, $\nu_p(m) \leq \nu_p(n)$ が成り立つことである.

そして, $\displaystyle \nu_p(N!)=\sum_{n=1}^N \nu_p(n)$ は $N$ について単調増加である.

以上から, $K$ の素因数分解を $K=p_1^{e_1} \dots p_r^{e_r}$ とすると, $N!$ が $K$ の倍数であることと, 以下の条件 $(*)$ は同値である.

$(*)$ 任意の $j=1,2, \dots, r$ に対して, $\displaystyle \sum_{i=1}^\infty \left \lfloor \dfrac{N}{p^i} \right \rfloor \nu_p(n) \geq e_j$

不等式において右辺は $N$ に依らない定数, 右辺は $N$ に関して単調増加である. よって, 全体の条件も $N$ に関して単調増加である. また, $K!$ は明らかに $K$ の倍数である. よって, $1$ 以上 $K$ 以下の範囲で $(*)$ を満たすような最小の整数 $N$ を二分探索で見つけることが出来る.

計算量については $K$ の素因数分解が $O(\sqrt{K})$ 時間, $K$ の素因数の個数 $r$ が $r=O(\log K)$ であることに注意すると, 1つの $N$ について $(*)$ を満たしているかどうかの確認は各 $j$ について $i \leq \log_p N$ の範囲を調べればよいので, $O(\log N)$ 時間である. よって, $(*)$ 全体では $N \leq K$ より $O((\log K)^2)$ 時間である. よって, 二分探索で $(*)$ を満たす最小の $N$ を見つけるのに $O((\log K)^3)$ 時間かかる.