2013年长沙网络赛G题

题目：http://acm.zju.edu.cn/changsha/showProblem.do?problemId=28

题意：给一个数n，范围是[2,80000]，使用加，乘运算和最多3个素数，有多少种方法使得结果恰好等于n。

分析：先素数筛选，然后我们可以看出，设有3个素数a，b，c，那么有如下几种情况。

a + b + c = n;

a + b = n;

a + b*c = n;

a*b = n;

a*b*c = n;

a = n;

那么我们可以用背包的思想来预处理，然后询问即可。

#include <iostream>#include <string.h>#include <stdio.h>using namespace std;const int N = 80005;const int MOD = 1000000007;bool prime[N];int p[N],cnt;int dp1[N][4],dp2[N][4];void isprime(){    cnt = 0;    int i,j;    memset(prime,true,sizeof(prime));    for(i=2;i<N;i++)    {        if(prime[i])        {            p[cnt++] = i;            for(j=i+i;j<N;j+=i)            {                prime[j]=false;            }        }    }}void Work(){    dp1[0][0] = 1;    dp2[1][0] = 1;    for(int i=0; i<cnt; i++)    {        for(int j=0; j<N&&p[i]+j<N; j++)        {            for(int k=0; k<=2; k++)                dp1[j+p[i]][k+1] = (dp1[j+p[i]][k+1] + dp1[j][k]) % MOD;        }    }    for(int i=0; i<cnt; i++)    {        for(int j=0; j<N && p[i]*j<N; j++)        {            for(int k=0; k<=2; k++)                dp2[j*p[i]][k+1] = (dp2[j*p[i]][k+1] + dp2[j][k]) % MOD;        }    }    for(int i=0; i<cnt; i++)    {        for(int j=0; j<N&&j+p[i]<N; j++)            dp1[j+p[i]][3] = (dp1[j+p[i]][3] + dp2[j][2]) % MOD;    }}int main(){    isprime();    Work();    int n;    while(~scanf("%d",&n))    {        int ans = 0;        for(int i=1; i<=3; i++)        {            ans = (ans+dp1[n][i]) % MOD;            if (i != 1)                ans = (ans+dp2[n][i]) % MOD;        }        printf("%d\n",ans);    }    return 0;}