ABC280D - Factorial and Multiple

解法1：

考え方

Editorial - Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280)

素因数分解：Pythonで蟻本2-6 - 数学的な問題を解くコツ - 競プロはじめました

回答例

from collections import defaultdict

K = int(input())

prime = defaultdict(int)
i = 2
while i * i <= K:
    while K % i == 0:
        prime[i] += 1
        K //= i
    i += 1
if K != 1:
    prime[K] += 1

ans_global = 0
for key in prime:
    ans_local = key
    cnt = prime[key]
    while True:
        tmp = ans_local
        while tmp % key == 0:
            tmp //= key
            cnt -= 1
            if cnt == 0:
                break
        if cnt == 0:
            break
        ans_local += key
    ans_global = max(ans_global, ans_local)

print(ans_global)

解法2：二分探索 & ルジャンドルの定理

考え方

Editorial - Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280)

回答例

from collections import defaultdict

K = int(input())

KK = K
prime = defaultdict(int)
i = 2
while i * i <= KK:
    while KK % i == 0:
        prime[i] += 1
        KK //= i
    i += 1
if KK != 1:
    prime[KK] += 1

def f(x, p, num):
    cnt = 0
    while x:
        cnt += x // p
        x //= p
    if cnt >= num:
        return True
    return False

ans = 0
for key in prime:
    ok, ng = K, 1
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if f(mid, key, prime[key]):
            ok = mid
        else:
            ng = mid
    ans = max(ans, ok)

print(ans)

二分探索の部分は以下でもok

def f(x):
    for key in prime:
        cnt = 0
        xx = x
        while xx > 1:
            cnt += xx // key
            xx //= key
        if cnt < prime[key]:
            return False
    return True

ok, ng = K, 1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if f(mid):
        ok = mid
    else:
        ng = mid

print(ok)