PythonでJOI難易度5を埋める #4

factorial - 階乗 (Factorial)

考えたこと
素因数分解して、それぞれの素因数が丁度入るような数を探していって、条件を満たす数の最大値を取ります。 素因数が丁度入るような数は、前から見ていくと大きい素数が出てくると厳しいので、†二分探索†を使います。

n = int(input())

def factorization(n):
    arr = []
    temp = n
    for i in range(2,int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i,cnt])
    if temp != 1:
        arr.append([temp,1])

    if arr == []:
        arr.append([n,1])

    return arr

f = factorization(n)
f.sort(reverse=True)

ans = []
for i in range(len(f)):
    f_n = f[i][0]
    f_c = f[i][1]
    high = 10 ** 8
    low = 0
    while high - low > 1:
        mid = (high + low) // 2
        cnt = 0
        c = 1
        while mid >= f_n ** c:
            cnt += mid // f_n ** c
            c += 1
        if cnt >= f_c:
            high = mid
        elif cnt < f_c:
            low = mid
        #print(high,mid,low)
    ans.append(high)

#print(ans)
print(max(ans))