P1463 [POI2001] [HAOI2007] 反素数 （DFS）

题目链接：

https://www.luogu.com.cn/problem/P1463

找最大的g(x)，如果最大值相同，x最小。

由算数基本定理：数x的约数个数是∏(ci+1)。n最大是2e9，2^31>2e9，2*3*5*...*31>2e9。

由此可知：1.ci之和一定不超过30；2.最大的质数不超过29。

由贪心，要找不超过n的最大的反质数，选择的质数要尽量小，这样相乘的结果越不容易超过n，且指数ci也越多。

解法：找一个数2^c1*3^c2*...29^c10。确定c1到c10的取值，且保证单减。所以我们考虑DFS，依次确定指数，记录前一个指数用来保证单减，再记录当前dfs的质数的编号，更新答案。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int p[12] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
ll n, ans, cnt;
void dfs(ll x, int m, int a, int c) {
	if (m > cnt || (m == cnt && x < ans))
		ans = x, cnt = m;//更新答案
	ll res = 1;
	for (int i = 1; i <= c; i ++) {//枚举指数
		res *= p[a];
		if (x * res > n) break;
		dfs(x * res, m * (i + 1), a + 1, i);
	}
}
int main() {
	cin >> n;
	dfs(1, 1, 1, 30);//当前数字大小，约数个数，当前质数的编号，上一个数的指数 
	cout << ans;
}