搜索
经典搜索题目（其实是蒟蒻只会搜……vfleaking好像有更优秀的做法？）
枚举质数的幂，其实深度没多大……因为$2^32$就超过N了……而且质数不能取的太大，所以不会爆……
/**************************************************************
Problem: 1053
User: Tunix
Language: C++
Result: Accepted
Time:40 ms
Memory:1760 kb
****************************************************************/ //BZOJ 1053
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=2e9,INF=~0u>>;
typedef long long LL;
/******************tamplate*********************/
int n,prime[],tot;
LL mx=,ans=;
bool vis[];
//第x个质数，总乘积为now，因数个数为m
void dfs(int x,LL now,LL m,int lim){
if (m>mx && now<=n){
mx=m; ans=now;
}
if (m==mx && now<ans && now<=n) ans=now;
if (x>) return;
LL p=now;
F(i,,lim){
if (p*prime[x]>n) break;
p*=prime[x];
dfs(x+,p,m*(i+),lim-i);
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1053.in","r",stdin);
freopen("1053.out","w",stdout);
#endif
scanf("%d",&n);
F(i,,sqrt(N)){
if (!vis[i]){
prime[++tot]=i;
for(int j=i*i;j<=sqrt(N);j+=i) vis[j]=;
}
}
dfs(,,,);
printf("%lld\n",ans);
return ;
}
1053: [HAOI2007]反素数ant
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1821 Solved: 1014
[Submit][Status][Discuss]
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