题目描述

题目：求不大于n的反素数
解释：求1~n中约数个数最多的数中最小的那一个

前置知识

n=$p_1^{c_1}$+$p_2^{c_2}$+…+$p_n^{c_n}$($p_i$是质数，$c_i$是它的指数)的约数个数是($c_1$+1) x ($c_2$+1) x … x ($c_n$+1)

算法

(dfs+剪枝)

剪枝

剪枝1：答案的质因数只可能是前10个素数（前11个素数的1次方相乘已超过范围，若有更大的质因数可将它换为更小的但没出现过的质因数，约数个数不变，数更小）
剪枝2：每个质因数质数最多是30次方（2的31次方已超过范围）
剪枝3：指数单调不增（如果一个大的质因数的指数比一个小的质因数的指数大，不妨将他们指数交换，约数个数不变，数更小）

C++ 代码

#include<bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
ll n,ans=1,sum=1;
int p[15]={0,2,3,5,7,11,13,17,19,23,29,31,37};//质数数组
iline ll po(int x,int c){//求x^c
    ll res=1;
    for(ri i=1;i<=c;i++) res*=x;
    return res;
}
void dfs(ll x,ll tot,int pos,int last){//现在数的大小、现在约数的个数、现在枚举到第几个质因数、上一个质因数的指数是多大
    if(x>n||pos>11){return;}//如果当前数已超出范围or枚举的质数超过前十个
    if(tot==sum&&x<ans) ans=x;
    //如果当前约数个数等于当前最大约数个数，但当前数比约数个数最大时的数更小，更新答案
    if(tot>sum) sum=tot,ans=x;
    //如果当前约数个数大于当前最大约数个数，更新答案
    for(ri i=0;i<=last;i++)//枚举放当前位置质因数的几次方
      if(po(p[pos],i)<n)
        dfs(x*po(p[pos],i),tot*(ll)(i+1),pos+1,i);
}
int main(){
    scanf("%lld",&n);
    dfs(1,1,1,31);
    printf("%lld\n",ans);
    return 0;
}

有问题下面随时留言，看到就回复
（这么良心的题解不点个赞再走嘛QwQ）