反素数

198. 反素数 - AcWing题库

 最大的反素数也就是约数个数最多的数中最小的那个数，可以考虑分解质因子形式

2、3、5、7、11、13、17、19、23、29这些，还有每个质因子的指数一定大于等于下一个质因子的指数，这样可以保证约数最多的时候数字尽可能小。

爆搜9个质因子，复杂度不会算，但实测dfs只会跑几千次。

#include
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long ll;
typedef long double ld;
 
int primes[9] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
 
int n;
int num, maxd;//数字和因子个数 
 
void dfs(int u, int last, int p, int cnt)
{
	if(cnt > maxd || cnt == maxd && p < num)
	{
		maxd = cnt;
		num = p;
	}
	
	if(u == 9)return;
	
	for(int i = 1; i <= last; i ++)
	{
		if((ll)p * primes[u] > n)break;
		p *= primes[u];
		dfs(u + 1, i, p, cnt * (i + 1));
	}
}
 
int main()
{
	IOS
	cin >> n;
	
	dfs(0, 31, 1, 1);
	
	cout << num;
	
	return 0;
}