解题报告 P1832 A+B Problem（再升级）（质数和方案）

题目内容

P1832

大意：求 n 被分解成若干个素数之和的方案总数

解题思路

打表出奇迹其实这东西不用完全打表，但是打质数表还是很重要的。

思路就是将 [1,n] 间的质数打出表，然后进行完全背包的求方案数即可，抽象的模型就是有 tot 件物品，每件物品的重量为这个质数的值，然后可以取无限次，求能凑出 n 重量的方案数。

不开 long long 见祖宗

#include <cstdio>
#include <cstring>
typedef long long ll;

const int maxn=1100;
ll n,f[maxn];
bool isprime[maxn];
int tot,prime[maxn];//tot为质数的个数，prime为质数的表。

void make_prime()//埃氏筛即可
{
    memset(isprime,1,sizeof(isprime));
    isprime[1]=isprime[0]=0;
    for(int i=2;i<=n;i++)
    {
        if(!isprime[i]) continue;
        for(int j=2;i*j<=n;j++) isprime[i*j]=0;
    }
    for(int i=2;i<=n;i++)
        if(isprime[i])
            prime[++tot]=i;
    return;
}

int main()
{
    scanf("%lld",&n);
    make_prime();
    f[0]=1;//一定记得初始值
    for(int i=1;i<=tot;i++)
        for(int j=prime[i];j<=n;j++)
            f[j]+=f[j-prime[i]];//求方案数的转移方程
    printf("%lld\n",f[n]);
    return 0;
}