题目链接

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

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

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

正解是枚举所有质数的次幂
来举个活生生的例子，免得以后忘记，比如说

首先枚举所有质数乘起来的1次幂，并且乘起来还要小于210，那么就是：
$2^1,2^13^1,2^13^15^1,2^13^15^17^1 </annotation> </semantics> </math>$

#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;
	}
}

牛客牛客想开了大赛2 【一】n的约数 【n以内约数个数最多的数】

文章目录

题目链接

牛客牛客想开了大赛2 【一】n的约数【n以内约数个数最多的数】