年会小游戏

题目链接：luogu U137970

题目大意

问你 1~n 中那个数的因子最多，最多是多少，如果有同样多的则输出小的那个。

思路

似乎没有什么优秀的方法，那我们就暴搜叭~

当然要剪枝，不然过不去呢~

我们考虑这么一个算数因数个数的方法。
如果一个数被表示为 ∏ i = 1 x p i k i \prod\limits_{i=1}^xp_i^{k_i} i=1∏x​piki​​，那这个数因数的个数就是： ∏ i = 1 x ( k i + 1 ) \prod\limits_{i=1}^x(k_i+1) i=1∏x​(ki​+1)。
（每个质数选 0 ∼ k i 0\sim k_i 0∼ki​ 个都为不同的）

首先我们小贪一些得出一些结论：

大的质数用的次数一定不会超过小的质数用的次数。
因为如果这样那我们还不如两个质数的次数交换，那贡献相同，整个数还变小的可能更优。

用的质数不超过 15 15 15 个。（最大的那个是 47 47 47）
计算器算一下就知道了，而且一定是从小到大的质数因为上面的条件。
（如果中间断了就是有一个质数的次数是 0 0 0，那根据上面的后面的次数都要是 0 0 0）

每个质数的次数肯定不会超过 60 60 60。
也是计算器算一些， 2 60 2^{60} 260。

然后注意一下乘的时候可能会爆 long long，所以要先判乘起来是否 > n >n >n。
而且乘的时候转成 long double，乘的时候就会爆了。

然后好像就没什么了。

代码

#include<cstdio>
#define ll long long

using namespace std;

int T;
ll n, prime[16] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};//最多乘15个不同的质数
ll now_, ans_;

void work(ll now, int nm, int maxdeg, ll ans) {
	if (ans > ans_) {
		ans_ = ans; now_ = now;
	}
	else if (ans == ans_ && now_ > now) now_ = now;
	
	if (nm > 15) return ;
	for (int i = 0; i <= maxdeg; i++) {//小剪枝，显然你大质数用的个数不可能比小质数用的多
		work(now, nm + 1, i, ans * (1 + i));
		if ((long double)now * (long double)prime[nm] > (long double)n) break;//要用 long double 不然乘了会炸 long long
		now = now * prime[nm];
	}
}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%lld", &n);
		
		ans_ = 1; now_ = n;
		work(1, 1, 60, 1);//一个最多用 60 次（2^60）
		
		printf("%lld %lld\n", now_, ans_);
	}
	
	return 0;
}