记录编号	220509	评测结果	AAAAAAAAAAAAAAAAAAAAAA
题目名称	[POI 2001]反素数	最终得分	100
用户昵称	stone	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2016-01-18 20:01:33	内存使用	0.74 MiB

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll N, Out_ans = 0x3f3f3f3f, ansv = 0;
int prime[50000 + 5], num[50000 + 5], cnt = 0;
bool vi[50000 + 5];

void getprime(int n){
  for(int i = 2; i <= n; ++ i){
	if(!vi[i]){
	  prime[++ cnt] = i;
	}
	for(int j = 1; j <= cnt && prime[j] * i <= n; ++ j){
	  vi[prime[j] * i] = true;
	  if(i % prime[j] == 0) break;
	}
  }
}

void dfs(int dep, ll nowv, int ans){
  if(dep > cnt) return;
  if(nowv > N) return;

  if(ans >= ansv){
	if(ans == ansv)
	  Out_ans = min(nowv, Out_ans);
	if(ans > ansv)
	  Out_ans = nowv;
	ansv = ans;
  }

  ll power; int t;
  for(power = prime[dep], t = 1; 1LL * nowv * power <= 1LL * N; power = 1LL * power * prime[dep], ++ t){
	dfs(dep + 1, nowv * power, ans * (t + 1));
  }
}

//#define ONLINE_JUDGE
int main(){
#ifndef ONLINE_JUDGE
  freopen("ant.in", "r", stdin);
  freopen("ant.out", "w", stdout);
#endif
  
  getprime(50000);
  scanf("%lld", &N);

  dfs(1, 1, 1);

  printf("%lld", Out_ans);

#ifndef ONLINE_JUDGE
  fclose(stdin); fclose(stdout);
#endif
  return 0;
}