C++14(g++5.4) 解法, 执行用时: 256ms, 内存消耗: 225852K, 提交时间: 2020-06-12 19:52:44

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,flag[N],p[N],tot,dp[200][N];
double val[N],f[200][N];
signed main(){
	scanf("%d",&n);
	for (int i=2;i<=n;i++)
		if (!flag[i])for (int j=2*i;j<N;j+=i)flag[j]=1;
	int sum=0;
	for (int i=1;i<=n;i++)val[i]=log(i);	
	for (int i=2;i<=n;i++)
		if (!flag[i]){
			p[++tot]=i;
			sum+=i;
			if (sum>=n)break;
		}
	for (int i=1;i<=tot;i++)
		for (int j=0;j<=n;j++)
			for (int k=0,s=1,s2=0;;s*=p[i],s2+=s,k++){
				if (s2>j)break;
				if (val[k+1]+f[i-1][j-s2]>f[i][j])f[i][j]=f[i-1][j-s2]+val[k+1],dp[i][j]=k;
			}
	long long ans=1;int t=n;
	for (int i=tot;i;i--){
		int k=dp[i][t];
		for (int j=0,s=p[i];j<k;j++,s*=p[i])t-=s;
		(ans*=k+1)%=1000000007;
	}
	printf("%lld\n",ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 569ms, 内存消耗: 2044K, 提交时间: 2020-07-29 17:47:04

#include<bits/stdc++.h>
using namespace std;

pair<double,int>DP[100005],t;
const int mod=1e9+7;
int L=0,T[50005];
bool V[100005]={0};
int main()
{
    int i,j,k,x,y,tp,s=0,n;
    scanf("%d",&n);
    for(i=2;i<=1e5;i++)
    {
    	if(!V[i])T[L++]=i;
    	for(j=0;j<L&&i*T[j]<=n;j++)
    	{
    		V[i*T[j]]=1;
			if(i%T[j]==0)break;
		}
	}
	for(tp=0;tp<L;tp++)
	{
		s+=T[tp];
		if(s>n)break;
	}
	DP[0].first=0,DP[0].second=1;
	for(i=0;i<=tp;i++)
		for(j=n;j>=1;j--)
			for(x=y=T[i],k=1;x<=j;k++,y*=T[i],x+=y)
			{
				t.first=DP[j-x].first+log2(k+1),t.second=DP[j-x].second*(k+1)%mod;
				DP[j]=max(t,DP[j]);
			}
	t.first=0,t.second=1;
	for(i=1;i<=n;i++)t=max(t,DP[i]);
	printf("%d\n",t.second);
    return 0;
}