题目描述
对于任何正整数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（1<=N<=2,000,000,000）。
输出格式
不超过N的最大的反质数。
输入输出样例
输入 #1
1000
输出 #1
840
2019/8/21-更新（代码后面写不了了，只能写在前面...）：
上午刚做的题，下午老师就讲了，搞得我好像白写了题解o(一︿一+)o，所以就顺便把老师的课件附上来吧！
（别忘了后面还有我自己写的...
首先普及下关于“反素数”的两个性质：
性质一:一个反素数的质因子必然是从2开始连续的质数.
性质二:p=2^t1*3^t2*5^t3*7^t4.....必然t1>=t2>=t3>=....
然后，我再说下我个人的理解
因为题目给出了n的范围，所以我们可得出结论：n的质因子的种数不超过10，所以得到了一条递归边界；
因为“反素数”的性质二，所以在两个数约数相等的情况下，更小的那个数就是“反素数”（可以用反证法证明：如果存在a的约数个数与b相等，且a>b。若认为a为“反素数”，那么不满足小于a的数的约数个数都小于a的约数个数，矛盾；）。所以我们要求的答案显然就是不大于n的 约数个数最大的 最小的数（哇这句话真的要好好理解，性质二肥肠关键！；
那么应用到本题，在递归的过程中，如果遇到两个数约数个数相同，并且当前得到的数now小于之前得到的数ans，那就更新ans；如果当前求得的数now的约数个数num已经大于之前求到的最大的约数个数tot，那就更新tot，并且别忘了也要更新ans；
如果在递归过程中，当前求得值已经大于n，那么就没必要再继续递归下去，直接返回，这就是第二条递归边界；
在递归函数中设置一个循环，每进行一个循环，当前递归的质因子的个数就加一，并且此处还可以进行一点剪枝，在循环条件中加入“当前递归的质因子个数 不大于 比其小的质因子的 个数”这个条件；
我在这里给出两种代码，思想大概就是我上面所述，只不过写法略有不同，大家可以选择自己更喜欢的一种啦~
（顺便，看我码字不易，怎么说也给个“推荐”吧♪(＾∀＾●)ﾉ
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+,inf=0x3f3f3f3f;
int a[]={,,,,,,,,,,};//打表大法好（质因子种数不超过10）
long long n,ans,tot;//tot为求到的最大的约数个数
void f(long long x,long long now,long long shu,long long num)
{
//x为当前递归的质因子，now为当前求得的数，num为now的约数个数
if(x==)return ;//递归边界1
long long tmp=,i;
for(i=;i<=shu;i++)//当前递归的质因子的个数不超过shu（想不到其他变量名惹...无奈词汇量太小）
{
tmp*=a[x];//tmp暂时存储
if(now*tmp>n)return ;//递归边界2
if(num*(i+)==tot&&now*tmp<ans)ans=now*tmp;//如果约数个数相同，并且当前得到的数now小于之前得到的数ans，那就更新ans；
if(num*(i+)>tot)//如果now的约数个数num大于之前求到的最大的约数个数tot，那就更新tot，并且更新ans；
{
tot=num*(i+);
ans=now*tmp;
}
f(x+,now*tmp,i,num*(i+));//往下递归
}
}
int main()
{
cin>>n;
f(,,,);
printf("%lld",ans);
return ;
}
我比较喜欢下面的代码↓↓↓
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+,inf=<<;
int a[]={,,,,,,,,,,},used[];//used[i]是指表中第i个质因子的个数
long long n,ans,tot;
void f(long long id,long long now,long long num)
{
//id指当前递归的是表中的第几个质数，now和num同上一种做法
if(num>tot)//同上一种做法
{
ans=now;
tot=num;
}
if(num==tot&&now<ans)ans=now;//同上一种做法
used[id]=;//注意每次递归要更新
while(now*a[id]<=n&&used[id]+<=used[id-])//循环条件中也包含了递归边界2（然鹅这里没有用递归边界1
{
now*=a[id];//now更新
used[id]++;//当前递归的质因子个数加一
f(id+,now,num*(used[id]+));//继续递归
}
}
int main()
{
cin>>n;
used[]=inf;//注意！要保证在对第一个质数进行递归的时候，循环可以进行下去，详见used[id]+1<=used[id-1]
f(,,);
printf("%lld",ans);
return ;
}