693. Antiprime数
★★ 输入文件：antip.in 输出文件：antip.out 简单对比
时间限制：1 s 内存限制：128 MB
如果一个自然数n（n>=1），满足所有小于n的自然数（>=1）的约数个数都小于n的约数个数，则n是一个Antiprime数。譬如：1, 2, 4, 6,
12, 24。
任务：
编一个程序：
1、
从ANT.IN中读入自然数n。
2、
计算不大于n的最大Antiprime数。
3、将结果输出到ANT.OUT中。
输入(
antip.in)：
输入文件antip.in只有一个整数，n（1
<= n <= 2 000 000 000）。
输出(antip.out):
输出文件antip.out也只包含一个整数，即不大于n的最大Antiprime数。
样例输入(
antip.in):
1000
样例输出(antip.out)：
840
问题描述:(转载自vb4896)
对于任何正整数x,起约数的个数记做g(x).例如g(1)=1,g(6)=4.
定义：如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数.
现在给一个N,求出不超过N的最大的反素数.
比如:输入1000 输出 840
思维过程:
求[1..N]中最大的反素数-->求约数最多的数（约数同样多取数值小的）
简单证明：
如果X是答案，但X不是约数最多的数，假设约数最多的数是Y，那么Y>X，否则不符合反质数的定义。
那么很明显Y也是一个反质数，且Y比X大，那么答案应该是Y而不是X。
如果求约数的个数 756=2^2*3^3*7^1
(2+1)*(3+1)*(1+1)=24
基于上述结论,给出算法:按照质因数大小递增顺序搜索每一个质因子,枚举每一个质因子
为了剪枝:
性质一:一个反素数的质因子必然是从2开始连续的质数.
因为最多只需要10个素数构造:2,3,5,7,11,13,17,19,23,29
性质二:p=2^t1*3^t2*5^t3*7^t4.....必然t1>=t2>=t3>=....
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
int prime[]={,,,,,,,,,,};
//2*3*5*7*11*13*17*19*21*23>n，所以只需考虑到23即可
ll n,BestSum,BestNum;
//当前走到num这个数，接着用第k个素数，num的约数个数为sum，
//第k个素数的个数上限为limit
void solve(ll num,ll sum,ll limit,ll k){
if(sum>BestSum){
BestSum=sum;
BestNum=num;
}
else if(sum==BestSum&&num<BestNum){//约数个数一样时，取小数
BestNum=num;
}
for(int i=;i<=limit;i++){//素数k取i个
num*=prime[k];
if(num>n) return ;
solve(num,sum*(+i),i,k+);
}
}
int main(){
freopen("antip.in","r",stdin);
freopen("antip.out","w",stdout);
cin>>n;
solve(,,,);
cout<<BestNum;
return ;
}