对于任何正整数x,其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足:g(x)>g(i) 0<i<x,则称x为反质数。例如,整数1,2,4,6等都是反质数。现在给定一个数N,你能求出不超过N的最大的反质数么?
对于任意正整数,其可表示为N = ${p_1}^{k1} \* {p_2}^{k2} * … * {p_j}^{kj} $ (p为质因子,k为指数)
其因子个数记为S(N), S(N) = $(1 + k1) * (1 + k2) * (1 + kj)$
根据反素数定义可以得出,因子数相同情况下,选择的值应该是最小的
那么假设S(a) == S(b), $a,b∈{N_+}$,
$a = {2 ^ 3} * {3 ^ 2} = 8 * 9 = 72$
$b = {2 ^ 2} * {3 ^ 3} = 4 * 9 = 36$
可以发现因子数相同情况下,b的值更符合反质数的定义, 得出结论$k1 <= k2 <= … <= kj$
基于此结论得出,假设指数都为1, 那么${p_1} * {p_2} * … *{p_j}$, j不会超过20个(假设n<=1e18)
因此可以先预处理出所有的p(质因子), 然后暴力(DFS)枚举每一个p的指数, 由于结论ki<=kj,i<j(剪枝), 所以时间复杂度必定不会太大
primes = []
def get_primes():
global n
for i in range(2, 999):
flag = False
for j in range(2, i - 1):
if i % j == 0: flag = True
if not flag: primes.append(i)
sum = 1
for x in primes:
sum *= x
if sum > n:
return
res, Max = 0, 0 # 表示最大值和因子个数
# 分别表示当选了哪一个质因子,前一个质因子的指数,因子个数,累乘和
def dfs(u, last, cnt, s):
# print(u, last, cnt, s)
global res, Max, n
if u >= len(primes): return # 超出选择范围
if cnt > Max or (cnt == Max and s < res): #选择因子数多的 或者 根据反素数定义,选择因子数相同,值最小的
res, Max = s, cnt
# 枚举当前质因子指数
for i in range(1, last + 1):
# 一定要用当前层的s值去累乘
# 例子: n=2, 这时候第一层的s=1, 进入下一层时候s=2,选择因子3去乘发现大于n返回上一层,这时候如果不用
# s去记录累乘,那么返回上一层时候需要的值是2,但实际值是刚进入的s=1,而i=2
s *= primes[u]
if s > n: break
dfs(u + 1, i, cnt * (i + 1), s)
n = int(input())
get_primes()
dfs(0, 100, 1, 1)
print(res)