摘要
Title: 198. 反素数
Tag: 约数个数、DFS
Memory Limit: 64 MB
Time Limit: 1000 ms

198. 反素数

题意

对于任何正整数 x，其约数的个数记作 g(x)，例如 g(1)=1、g(6)=4。
如果某个正整数 x 满足：对于任意的小于 x 的正整数 i，都有 g(x)>g(i)，则称 x 为反素数。
例如，整数 1，2，4，6 等都是反素数。
现在给定一个数 N，请求出不超过 N 的最大的反素数。
思路

首先看到不超过N，先去考虑数据范围
- 1~N中任何数的不同质因子都不会超过10个,因为 $2*3*5*7*11*13*17*19*23*29*31>2*10^9$ ,
- 且所有质因数的指数总和不超过30,因为 $2^31>2*10^9$ .
其次分析题意得到，1_{N中最大的反质数,就是1}N中约数个数最多的数中最小的一个
最后x的质因子是连续的若干个最小的质数,且质数的指数单调递减（这样保证用到的素因子最多）

所以就根据上面的性质，总次数不超过30

代码

'''
Author: NEFU AB-IN
Date: 2022-03-10 15:25:23
FilePath: \ACM\Acwing\198.py
LastEditTime: 2022-03-10 16:55:56
'''

import sys

sys.setrecursionlimit(int(2e9))

ps = [0, 2, 3, 5, 7, 11, 13, 17, 19, 23]
maxn = 0  #最多约数数量
ans = 0  #答案


def dfs(u, prod, last, res):  #这个素因子的下标、乘积、上一个素因子的幂、因子个数
    global ans, maxn
    if res > maxn or (res == maxn and prod < ans):
        ans = prod
        maxn = res
    if u == 9:
        return
    for i in range(1, last + 1):
        if prod * ps[u] > n:
            break
        prod *= ps[u]
        dfs(u + 1, prod, i, res * (i + 1))


n = int(input())
dfs(1, 1, 30, 1)

print(ans)

198. 反素数

题意

思路

代码