洛谷P1463 [POI2001][HAOI2007] 反素数

对于任何正整数 xx，其约数的个数记作 g(x)g(x)。例如 g(1)=1g(1)=1，g(6)=4g(6)=4。

如果某个正整数 xx 满足：forall 0 lt i lt x∀0g(i)，则称 xx 为反质数。例如，整数 1,2,4,61,2,4,6 等都是反质数。

现在给定一个数 NN，你能求出不超过 NN 的最大的反质数么？

一个数 NN。

不超过 NN 的最大的反质数。

输入 #1复制

1000

输出 #1复制

840

1 leq N leq 2 times 10^91≤N≤2×109

上代码：

#include
using namespace std;
int anst,a[15]= {1,2,3,5,7,11,13,17,19,23,29,31}; //当最大指数为1时乘到31就大于2*10~9了；anst记录因子个数。
long long ans,n;
int b[15]= {999}; //保存每个质数的指数，2可以无限增大，其余不大于前一个。
void dfs(int x,long long y,int cnt) { //x:因子个数。y:搜到的数。cnt：指针，表示当前要乘上第几个质数。
	x/=(b[cnt]+1); //若乘上第cnt个质数，因子数就变成 x/(b[cnt]+1)*(b[cnt]+2);
	y*=a[cnt];
	b[cnt]++;
	x*=(b[cnt]+1); //乘a[cnt]
	if(y>n) 
	{
		b[cnt]--;    //注意还原状态（回溯）。
		return;
	}
	if(x<=anst&&y>=ans) 
	{
		b[cnt]--;    //剪枝，若因子较少，且值较大，跳。
		return;
	}
	if(x>=anst) 
	{
		//若x>anst，那必然更新。若等于，则y>n;
	dfs(1,1,1);
	cout<