原题链接

题目描述

对于任何正整数x，其约数的个数记作g(x)，例如g(1)=1、g(6)=4。

如果某个正整数x满足：对于任意的小于x的正整数 i，都有g(x)>g(i) ，则称x为反素数。

例如，整数1，2，4，6等都是反素数。

现在给定一个数N，请求出不超过N的最大的反素数。

输入格式
一个正整数N。

输出格式
一个整数，表示不超过N的最大反素数。

数据范围
$1≤N≤2∗10^9$

样例

输入样例：
1000
输出样例：
840

数学性质(质因数分解)

首先我们来三个性质

1~N中最大的反质数,就是1~N中约数个数最多的数中最小的一个.因为,如果不是最小的那一个,必然会出现$g(x)=g(i)$

1~N中任何数的不同质因子都不会超过10个,因为$2\*3\*5\*7\*11\*13\*17\*19\*23\*29\*31>2\*10^9$,且所有质因数的指数总和不超过30,因为$2^{31}>2\*10^9$.

x的质因子是连续的若干个最小的质数,且质数的指数单调递减.如果说我们选择的质数不是连续的,也就是$A_1\*A_3$,那么我还不如选择$A_1\*A_2$,因为这样数还更小.至于指数问题,如果说$c_1<c_2$,那么$c_1+1$,$c_2-1$会是的我们乘积更加小,而且约数个数不变.$x={A_1}^{C_1}\*{A_2}^{C_2}\*{A_3}^{C_3}\*......\* {A_n}^{C_n}$

根据上面一系列性质,我们得出了最简洁的思路,使用DFS,尝试确定前十个质数的指数,然后满足指数单调递减,总乘积不超过N,且同时记录约数的个数

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 2e9
ll zs[11]={0,2,3,5,7,11,13,17,19,23,29},c[11],ans=INF,cnt_ans=1,n;
void dfs(ll now, ll num, ll cnt)
{
    if (now==11) 
    {
        if (cnt>cnt_ans || (cnt==cnt_ans && ans>num))
        {
            cnt_ans=cnt;
            ans=num;
        }
        return;
    }
    ll num_cnt=num;
    for (int i=0;i<=c[now-1];i++)
    {
        if (num_cnt>n)
            return;
        c[now]=i;
        dfs(now+1,num_cnt,cnt*(i+1));
        num_cnt*=zs[now];
    }
}
int main() 
{
    cin>>n;
    c[0]=INF;
    dfs(1,1,1);
    cout<<ans<<endl;
    return 0;
}