bzoj 1053: [HAOI2007]反素数ant

1053: [HAOI2007]反素数ant

Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 2750  Solved: 1559 [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

HINT

Source

思路：dfs然后剪一下。。。和ural 1748同样的做法。。。。

还可以。。。打表。。。。

有表不打和咸鱼有什么区别呢

（oi赛制不可以带纸质材料，所以打表大概算是恶习...不过acm不一样啊orz。。。反素数表1..1E18也才167个。。。。

/* ***********************************************
Author :111qqz
Created Time :Wed 21 Sep 2016 08:15:41 PM CST
File Name :code/bzoj/1053.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
LL anti_prime[]={1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,554400,665280,720720,1081080,1441440,2162160,2882880,3603600,4324320,6486480,7207200,8648640,10810800,14414400,17297280,21621600,32432400,36756720,43243200,61261200,73513440,110270160,122522400,147026880,183783600,245044800,294053760,367567200,551350800,698377680,735134400,1102701600,1396755360,2095133040,2205403200,2327925600,2793510720,3491888400,4655851200,5587021440,6983776800,10475665200,13967553600,20951330400,27935107200,41902660800,48886437600,64250746560,73329656400,80313433200,97772875200,128501493120,146659312800,160626866400,240940299600,293318625600,321253732800,481880599200,642507465600,963761198400,1124388064800,1606268664000,1686582097200,1927522396800,2248776129600,3212537328000,3373164194400,4497552259200,6746328388800,8995104518400,9316358251200,13492656777600,18632716502400,26985313555200,27949074753600,32607253879200,46581791256000,48910880818800,55898149507200,65214507758400,93163582512000,97821761637600,130429015516800,195643523275200,260858031033600,288807105787200,391287046550400,577614211574400,782574093100800,866421317361600,1010824870255200,1444035528936000,1516237305382800,1732842634723200,2021649740510400,2888071057872000,3032474610765600,4043299481020800,6064949221531200,8086598962041600,10108248702552000,12129898443062400,18194847664593600,20216497405104000,24259796886124800,30324746107656000,36389695329187200,48519593772249600,60649492215312000,72779390658374400,74801040398884800,106858629141264000,112201560598327200,149602080797769600,224403121196654400,299204161595539200,374005201994424000,448806242393308800,673209363589963200,748010403988848000,897612484786617600,1122015605983272000,1346418727179926400,1795224969573235200,2244031211966544000,2692837454359852800,3066842656354276800,4381203794791824000,4488062423933088000,6133685312708553600,8976124847866176000,9200527969062830400};

int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif
	LL n,ans;
//	int cnt = 0 ;
//	for ( int i = 0 ; anti_prime[i]!=0 ; i++) cnt++;
//	cout<<"cnt:"<<cnt<<endl;
	scanf("%lld",&n);
	ans = upper_bound(anti_prime,anti_prime+167,n)-anti_prime-1;
	printf("%lld\n",anti_prime[ans]);

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