BZOJ

BZOJ 1053 反素数

题意

用g(x)表示x的约数个数，定义：若x满足g(x)>g(i){i|0< i< x}，则x被称为反素数。求不超过n的最大反素数。

数据范围

$$1\leq n\leq2000000000$$

题解

首先明白：一个数约数个数=所有素因子的指数+1的乘积 。
然后可以通过计算得:一个2000000000以内的数字不会有超过12个素因子，并且小素因子多一定比大素因子多要优。那么预处理出前12个素数，剩下的直接暴搜即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<cstdio>
const int p[13]={1,2,3,5,7,11,13,17,19,23,29,31};
int n,ans=1,num=1;
void dfs(int k,long long now,int cnt,int last)
//当前素数因子，当前数，约数个数，上一个素数因子指数
{
	if (k==12)
	{
		if ((now>ans&&cnt>num)||(now<ans&&cnt>=num))
			{ans=now;num=cnt;}
		return;
	}
	int t=1;
	for (int i=0;i<=last&&now*t<=n;i++)
	//较大素数因子指数比较小的小，才能保证相同约数个数时当前数尽量小
	{
		dfs(k+1,now*t,cnt*(i+1),i);
		t*=p[k];
	}
}
int main()
{
	scanf("%d",&n);
	dfs(1,1,1,20);
	printf("%d",ans);
	return 0;
}