经过指数递减优化为什么还TLE
查看原帖
经过指数递减优化为什么还TLE
559969
dtw35l楼主2024/5/22 14:37
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, ans, yue;
void dfs(int c1, int c2, int c3, int c4, int c5, int c6, int c7, int c8, int c9) {
	int x=pow(2,c1)*pow(3, c2)*pow(5,c3)*pow(7,c4)*pow(11,c5)*pow(13,c6)*pow(17,c7)*pow(19,c8)*pow(23,c9);
	int y = (c1+1)*(c2+1)*(c3+1)*(c4+1)*(c5+1)*(c6+1)*(c7+1)*(c8+1)*(c9+1);
	if (y > yue) yue = y, ans = x;
	if (y == yue) ans = min(ans, x);
	if (x * 2 <= n)              dfs(c1+1,c2,c3,c4,c5,c6,c7,c8,c9);
	if (x * 3 <= n && c2 < c1)   dfs(c1,c2+1,c3,c4,c5,c6,c7,c8,c9);
	if (x * 5 <= n && c3 < c2)   dfs(c1,c2,c3+1,c4,c5,c6,c7,c8,c9);
	if (x * 7 <= n && c4 < c3)   dfs(c1,c2,c3,c4+1,c5,c6,c7,c8,c9);
	if (x * 11 <= n && c5 < c4)  dfs(c1,c2,c3,c4,c5+1,c6,c7,c8,c9);
	if (x * 13 <= n && c6 < c5)  dfs(c1,c2,c3,c4,c5,c6+1,c7,c8,c9);
	if (x * 17 <= n && c7 < c6)  dfs(c1,c2,c3,c4,c5,c6,c7+1,c8,c9);
	if (x * 19 <= n && c8 < c7)  dfs(c1,c2,c3,c4,c5,c6,c7,c8+1,c9);
	if (x * 23 <= n && c9 < c8)  dfs(c1,c2,c3,c4,c5,c6,c7,c8,c9+1);
}

signed main() {
	cin >> n;
	dfs(0, 0, 0, 0, 0, 0, 0, 0, 0);
	cout << ans;
	return 0;
}
2024/5/22 14:37
加载中...