「BZOJ1053」反素数

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

引理 $1$：

$1\sim N$ 中最大的反素数，就是 $1\sim N$ 中约数个数最多的数中最小的一个。

引理 $2$：

$1\sim N$ 中任何数的不同质因子都不会超过 $10$ 个，且所有质因子的指数总和不超过 $30$。

引理 $3$：

$\forall x\in[1,N]$，$x$ 为反素数的必要条件是：$x$ 分解质因数后可写作 $2^{c_1}\times3^{c_2}\times 5^{c_3}\times …29^{c_{10}}$，且 $c_1\geq c_2\geq···\geq c_{10}\geq 0$。

即 $x$ 的质因子是连续的若干个最小的质数，并且指数单调递减。

直接用的DFS依次确定指数，即可。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
long long n,ans,maxx;
long long prime[11]={0,2,3,5,7,11,13,17,19,23,29};
void dfs(int num,int x,int p)//现在约数个数，现在的数，现在不同约数的个数
{
	if(num>maxx)
	{
		maxx=num;
		ans=x;
	}
	if(num==maxx&&x<ans)
		ans=x;
	if(p>11)
		return ;
	for(int i=1;i<=30;i++)
	{
		if(x*prime[p]>n)
			break;
		dfs(num*(i+1),x*prime[p],p+1);
		x*=prime[p];
	}
}
int main()
{
	scanf("%lld",&n);
	dfs(1,1,1);
	printf("%lld",ans);
    return 0;
}