次の判定問題を考えます。

整数 \(N, K\) が与えられる。\(N!\) は \(K\) の倍数か？

これが解ければ、\(N\) の値を二分探索することで答えを求めることができます。以下、この判定問題の解法を考えます。

ここで、ルジャンドルの定理 とよばれる次の定理が使えます。

\(n!\) が素数 \(p\) で割り切れる回数は、\(\displaystyle \sum_{i = 1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \cdots\) である。

この定理を用いれば、判定問題は

1. \(K\) を素因数分解する。
2. \(K\) のすべての素因数 \(p\) について、\((N! \ を \ p \ で割り切れる回数) \geq (K \ を \ p \ で割り切れる回数)\) が成り立っているか調べる。

というアルゴリズムで解けます。このアルゴリズムの計算量は、素因数分解がボトルネックで \(O(\sqrt{K})\) です。素因数分解は \(1\) 回前計算すればよいので、全体でも \(O(\sqrt{K})\) で解くことができました。

Python による実装例：

k = int(input())

# 素因数分解
pes = list()  # 素因数 p と 指数 e の組を格納
k2 = k
p = 2
while p * p <= k:
  e = 0
  while k2 % p == 0:
    k2 //= p
    e += 1
  if e > 0:
    pes.append((p, e))
  p += 1
if k2 > 1:
  pes.append((k2, 1))

# n! は p で何回割り切れるか（ルジャンドルの定理）
def legendre(n, p):
  res = 0
  p2 = p
  while True:
    tmp = n // p2
    if tmp == 0:
      break
    res += tmp
    p2 *= p
  return res

# 判定問題
def isok(n):
  for p, e in pes:
    if legendre(n, p) < e:
      return False
  return True

# 二分探索
ng, ok = 1, k  # k ≥ 2 なので 1! は k の倍数にならない、また k! は必ず k の倍数
while abs(ok - ng) > 1:
  mid = (ok + ng) // 2
  if isok(mid):
    ok = mid
  else:
    ng = mid
print(ok)