题目 BZOJ1053 反素数

原题传送门

题目分析

那么关于这道题，首先来了解一下这 \(4\) 个引理（大家可以自己推一推这些引理）：

引理\(1\)：\(\left[1,N\right]\) 中最大的反素数，就是 \(\left[1,N\right]\) 中约数个数最多的数中最小的一个。

引理\(2\)：\(\left[1,N\right]\) 中任何数的不同质因子不会超过 \(10\) 个，且所有质因子的指数和不超过 \(30\) 。

引理\(3\)：\(x\) 的质因子是连续的若干个最小的素数，并且指数单调递减。即：

$ x = 2^{c_1} \times 3^{c_2} \times 5^{c_3} \times 7^{c_4} \times 11^{c_5} \times 13^{c_6} \times 17^{c_7} \times 19^{c_8} \times 23^{c_9} \times 29^{c_{10}}$，

且 \({c_1} ≥ {c_2} ≥ {c_3} ≥ \cdots ≥ {c_{10}} ≥ 0\)。

Code：

#include<cstdio>
#define ll long long
using namespace std;
int n,ans=1,num=1;
int p[15]={1,2,3,5,7,11,13,17,19,23,29,31};
void dfs(int k,ll now,int cnt,int last)
{
    if(k==11)
    {
        if(now>ans&&cnt>num){ans=now;num=cnt;}
        if(now<=ans&&cnt>=num){ans=now;num=cnt;}
        return;
    }
    int s=1;
    for(int i=0;i<=last;++i)
    {
        dfs(k+1,now*s,cnt*(i+1),i);
        s*=p[k];
        if(now*s>n)break;
    }
}
int main()
{
    scanf("%d",&n);
    dfs(1,1,1,15);
    printf("%d",ans);
    return 0;
}