反素数ant

时间限制: 1 Sec  内存限制: 128 MB

题目描述

对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足：g(x)>g(i) 0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。现在给定一个数N，你能求出不超过N的最大的反质数么？

 

输入

一个数N（1<=N<=2,000,000,000）。

 

输出

不超过N的最大的反素数。

 

样例输入

复制样例数据

1000

样例输出

840

一个数约束的个数：设这个数是由x1,x2,x3....乘起来的(xi都是素数),那么一个数的约数个数就是这些素数次数+1乘起来；

如 36 = 2^2*3^2,那么约数个数为(2+1)*(2+1)=9;

 

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

LL n;
int a[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};//没必要很多个素数，素数越大次数越小
LL maxx, ans;

void dfs(int num, LL sum, int tim, int pre){// pre表示前面的用了素数用了几次，肯定素数小的用的多才好
	if(num == 12){
		if(tim > ans && maxx < sum) maxx = sum, ans = tim;//次数多的并且这个数肯定比约数少的数大
		if(tim >= ans && maxx > sum) maxx = sum, ans = tim;//取次数相同时值最小的
		return ;
	}
	LL t = 1;
	for (int i = 0; i <= pre; i++){
		dfs(num + 1, sum * t, tim * (i + 1), i);
		t *= a[num];
		if(t * sum > n) break;
	}
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%lld", &n);
	dfs(0, 1, 1, n >> 1);
	printf("%lld\n", maxx);

	return 0;
}
/**/