C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 1692K, 提交时间: 2020-10-06 09:48:08

#include<iostream>
#include<cstdio>
using namespace std;
int n,t,p[1001];
long long ans,f[1001][1001];
bool ff[1001];
void get()
{
    for(int i=2;i<=1000;i++)
    {
      if(!ff[i])p[++t]=i;
      for(int j=1;j<=t&&i*p[j]<=1000;j++){ff[i*p[j]]=true;if(i%p[j]==0 )break; }
    }
}
void dp()
{
    f[0][0]=1;
    for(int i=1;i<=t;i++)
    {
      for(int j=0;j<=n;j++)f[i][j]=f[i-1][j];
      for(int j=p[i];j<=n;j*=p[i])
        for(int k=0;k<=n-j;k++)
           f[i][k+j]+=f[i-1][k];
    }
}
int main()
{
    cin>>n; 
    get();
    dp();
    for(int i=0;i<=n;i++)ans+=f[t][i];
    cout<<ans<<endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 380K, 提交时间: 2020-09-27 11:07:16

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

int main()
{
    int i,j,k,n,L=0,T[505];
    long long ans=0,DP[1005]={0};
    bool V[1005]={0};
    for(i=2;i<=1e3;i++)
    {
    	if(!V[i])T[L++]=i;
    	for(j=0;j<L&&i*T[j]<=1e3;j++)V[i*T[j]]=1;
	}
    scanf("%d",&n),DP[0]=1;
    for(i=0;i<L;i++)
    	for(j=n;j>=T[i];j--)
    		for(k=T[i];k<=j;k*=T[i])DP[j]+=DP[j-k];
    for(i=0;i<=n;i++)ans+=DP[i];
    printf("%lld\n",ans);
    return 0;
}