1053: [HAOI2007]反素数ant
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1497 Solved: 821
[Submit][Status]
Description
对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。
如果某个正整数x满足：g(x)>g(i) 0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。
现在给定一个数N，你能求出不超过N的最大的反质数么？
Input
一个数N（1<=N<=2,000,000,000）。
Output
不超过N的最大的反质数。
Sample Input
1000
Sample Output
840
HINT
Source
這種題應該是通過看數據範圍和解的密度可以發現這是打表，而實際證明連打表都不用，直接暴力構造搜索就行了，搜索中避免如下數字：質因數不連續，質因數過大。這樣解的空間就很小了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<string>
#include<queue>
using namespace std;
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
#define MAXN 11000000
#define MAXV MAXN*2
#define MAXE MAXV*2
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define MAXL 2100000000
typedef long long qword;
inline int nextInt()
{
char ch;
int x=;
bool flag=false;
do
ch=getchar(),flag=(ch=='-')?true:flag;
while(ch<''||ch>'');
do x=x*+ch-'';
while (ch=getchar(),ch<='' && ch>='');
return x*(flag?-:);
} int n,m;
int seq[MAXN],tops=-;
int prime[]={,,,,,,,,,,,,,,,,,,,,,,,,,,,,,};
struct aaa
{
int v,x;
}a[MAXN];
bool cmp_x(aaa a1,aaa a2)
{
return a1.x<a2.x;
}
int topa=-;
void search_m(qword now,int l,int tot)
{
int i;
int x;
if (l== || now>=MAXL)return ;
// cout<<now<<" "<<tot<<endl;
a[++topa].x=now;
a[topa].v=tot;
l++;
x=;
for (i=;i< && now<MAXL;i++)
{
now*=prime[l];
x++;
search_m(now,l,tot*x);
}
} int main()
{
freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int i,j,k;
int x,y,z;
int tot;
int mx=;
scanf("%d",&n);
search_m(,-,);
sort(a,a+topa+,cmp_x);
for (i=;i<=topa;i++)
{
if (a[i].v>mx)
{
mx=a[i].v;
if (a[i].x>n)
{
cout<<x<<endl;
return ;
}
x=a[i].x;
}
}
return ;
/* x=1;
mx=0;
for (i=1;i<=n;i++)
{
tot=0;
for (j=1;j<=i;j++)
{
if (i%j==0)tot++;
}
if (tot>mx)
{
mx=tot;
cout<<i<<" "<<tot<<" "<<endl;
x=i;
} }
cout<<endl;*/
return ;
}