文章目录

题目链接

https://ac.nowcoder.com/acm/contest/907/B

总感觉以前做过,但是没深入理解。。。

我一开始的超时代码是枚举所有的质数,这个非常好理解,但是这样会超时,复杂度也不知道咋算

正解是枚举所有质数的次幂
来举个活生生的例子,免得以后忘记,比如说 <math> <semantics> <mrow> <mn> 210 </mn> </mrow> <annotation encoding="application&#47;x&#45;tex"> 210 </annotation> </semantics> </math>210

首先枚举所有质数乘起来的1次幂,并且乘起来还要小于210,那么就是:
<math> <semantics> <mrow> <msup> <mn> 2 </mn> <mn> 1 </mn> </msup> <mo separator="true"> , </mo> <msup> <mn> 2 </mn> <mn> 1 </mn> </msup> <msup> <mn> 3 </mn> <mn> 1 </mn> </msup> <mo separator="true"> , </mo> <msup> <mn> 2 </mn> <mn> 1 </mn> </msup> <msup> <mn> 3 </mn> <mn> 1 </mn> </msup> <msup> <mn> 5 </mn> <mn> 1 </mn> </msup> <mo separator="true"> , </mo> <msup> <mn> 2 </mn> <mn> 1 </mn> </msup> <msup> <mn> 3 </mn> <mn> 1 </mn> </msup> <msup> <mn> 5 </mn> <mn> 1 </mn> </msup> <msup> <mn> 7 </mn> <mn> 1 </mn> </msup> </mrow> <annotation encoding="application&#47;x&#45;tex"> 2^1,2^13^1,2^13^15^1,2^13^15^17^1 </annotation> </semantics> </math>21,2131,213151,21315171
最多有4个质数连起来乘小于等于210
那么枚举所有质数乘起来的2次幂中连着乘的质数个数就不可能大于刚刚1次幂的4个质数
所以下一次进递归的时候枚举的质数个数一定小于上一次的,这是不超时的关键,必须要写
那么第二次枚举就是:
<math> <semantics> <mrow> <msup> <mn> 2 </mn> <mn> 2 </mn> </msup> <mo separator="true"> , </mo> <msup> <mn> 2 </mn> <mn> 2 </mn> </msup> <msup> <mn> 3 </mn> <mn> 2 </mn> </msup> </mrow> <annotation encoding="application&#47;x&#45;tex"> 2^2,2^23^2 </annotation> </semantics> </math>22,2232
看吧,最多才2个质数连着乘
当枚举3次幂的时候:
<math> <semantics> <mrow> <msup> <mn> 2 </mn> <mn> 3 </mn> </msup> </mrow> <annotation encoding="application&#47;x&#45;tex"> 2^3 </annotation> </semantics> </math>23
就只有2一个质数了(✪ω✪)

#include"bits/stdc++.h"
#define out(x) cout<<#x<<"="<<x
#define C(n,m) (m>n?0:(long long)fac[(n)]*invf[(m)]%MOD*invf[(n)-(m)]%MOD)
using namespace std;
typedef long long LL;
const int maxn=1e2+5;
const int MOD=1e9+7;
LL prime[17]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
LL N;
int res;
void dfs(int u,LL n,int ans,int mi)//第u个质数,枚举出来的所有质数的幂的乘积,临时的答案,枚举质数的次幂 
{
	if(u>16)return ;//第16个质数就是59,也就是说是从2开始连着乘的质数小于1e18的最大的质数 
	if(n>N)return ; 
	res=max(res,ans);
	for(int i=1;i<=mi;i++)//枚举所有质数的次幂
	{
		LL tp=pow(prime[u],i);
		if(tp>N)break;
		if(n>N/tp)break;
		dfs(u+1,n*tp,ans*(i+1),i);
	}
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		cin>>N;
		res=1;
		dfs(0,1,1,63);
		cout<<res<<endl;
	}
}