Antiprime数(0373)
问题描述
如果一个自然数n（n>=1），满足所有小于n的自然数（>=1）的约数个数都小于n的约数个数，则n是一个Antiprime数。譬如：1, 2, 4, 6, 12, 24。
任务：
编一个程序：
计算不大于n的最大Antiprime数。
输入
输入只有一个整数，n（1 <= n <= 2 000 000 000）
输出
输入只有一个整数，n（1 <= n <= 2 000 000 000）
样例输入
1000
样例输出
840
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
#define pb push_back
#define ll long long
#define INF 0x3f3f3f3f
#define N 2000000000 ll n;
ll res;
ll fac;
ll prime[]={,,,,,,,,,}; void dfs(ll x,ll y,ll z,ll last)
{
if(x>=){
if(z>fac) res=y,fac=z;
if(z==fac && y<res) res=y,fac=z;
return;
}
for(ll i=;i<=last;i++){
if(y>n) break;
dfs(x+,y,z*(i+),i);
y*=prime[x];
}
}
int main()
{
while(scanf("%lld",&n)!=EOF)
{
res=fac=;
dfs(,,,INF);
cout<<res<<endl;
}
return ;
}