PythonでJOI難易度5を埋める #4
考えたこと
素因数分解して、それぞれの素因数が丁度入るような数を探していって、条件を満たす数の最大値を取ります。
素因数が丁度入るような数は、前から見ていくと大きい素数が出てくると厳しいので、†二分探索†を使います。
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))