题目描述

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

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

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

输入格式
一个数 NN。

输出格式
不超过 NN 的最大的反质数。

输入输出样例

输入
1000

输出
840

说明/提示

1 ≤N≤2×109

题意分析:

神奇的结论

int a[]=质数 ,k[]=指数

n= a[1]^k[1] * a[2]^k[2] *……a[n]^k[n]

约数个数 t=(k[1]+1)(k[2]+1)……*(k[n]+1)

枚举每一个质数指数 搜最大答案

转念一想，这虽然比暴力好了许多，不过大概会挂

这时我们就要有一些优化的思路：

这些思路的主旨就是在约数个数相同的情况下尽可能地让当前数小

比如：

1、第一种情况：
6=23 10=25

这是一种约数不同的例子，所以我们枚举质数的时候要从小到大枚举

2、第二种情况：
12=22*3 18=32*2

这时一种指数不同的例子，所以我们就可以推得较大的质数的指数一定小于较小的质数的指数

其实这个很好理解，
就像 2333 比他小的2223 比他小但是因数却和他相等所以他不是反素数。

总结

反素数 质因数的指数一定是递减或者相等的（相等时得比较）。
具体看代码吧

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <bits/stdc++.h>
#define ll long long int
#define sc(a) scanf("%lld",&a)
const int mod=998244353;
using namespace std;
const int inf=1e9+7;
const int maxn=2e5+10;

ll n,m,sum,t,p,res;
ll a[maxn],b[maxn],c[maxn];
ll x,y;
ll dp[110][110];
ll maxx=-1,num=-1;

char str[maxn],s[maxn],ss[maxn];
ll prime[20]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,51};//前二十个素数

void dfs(int a,int b,int c,int d){
	ll i=a,j=0,nt;//a 是开始的值 b 为第几个素数 c 为因子数 d 最大指数也就是上一个的指数 
	while(j<d){
		if(c > maxx || ( c == maxx && a < num)) //两种情况 1, 指数个数比前面的要大,2,指数数相等但这个数比上个数要小 
		 num = a ,maxx = c;//更新小于n的最大反素数 
		j++;
		if(n/i<prime[b]) break;//这个数乘与j会大于n退出 
		nt=c*(j+1);//因子个数 
		i=i*prime[b];//更新这个数；
		if(i<=n) dfs(i,b+1,nt,j);
	}
}
int main(){
	sc(n);
	dfs(1,1,1,30);
	printf("%lld\n",num);
	return 0;
}