[USACO20OPEN] Exercise G

题面：Luogu
题解：
大概是和这个一样的
只是那个是求方案数，这个是求和
所以我们在转移时

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T& x)
{
    x=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
#define ll long long
#define maxn 10005
int prime[maxn],vis[maxn],pnum;
void eular(int maxnum=10000)
{
    for(int i=2;i<=maxnum;++i)
    {
        if(!vis[i]) prime[++pnum]=i;
        for(int j=1;j<=pnum&&i*prime[j]<=maxnum;++j)
        {
            vis[i*prime[j]]=1;
            if(!(i%prime[j])) break;
        }
    }
}
ll dp[maxn],m;
int main()
{
    int n;read(n);read(m);
    eular(n);
    dp[0]=1;
    for(int i=1;i<=pnum;++i)
        for(int j=n;j>=prime[i];--j)
            for(int k=prime[i];k<=j;k*=prime[i])
                dp[j]=(dp[j]+dp[j-k]*k)%m;
    ll sum=1;
    for(int i=1;i<=n;++i) sum+=dp[i],sum%=m;
    printf("%lld\n",sum);
    return 0;
}