题目描述:哥德巴赫猜想认为任一大于2的偶数,都可表示成两个素数之和,比如
6 = 2+2+2
6 = 3+3
10 = 2+2+2+2+2
10 = 2+2+3+3
10 = 2+3+5
10 = 3+7
像3+7与7+3只有顺序不一样的认为是一种方式
问:给定一个10000以内的偶数,将它表示为素数的和有几种方式?(结果对10^9+7取模)
分析:相当于求以质数为物品体积,背包容量为10000的,可以重复选择的背包,设p[i]是第i个质数,dp[i][n]表示把正整
数n拆分为不大于p[i]的若干质数和的方案数,则有dp[i][n]=dp[i-1][n]+dp[i][n-p[i]]
#include <iostream> #include <string.h> #include <stdio.h> #include <vector> using namespace std; typedef long long LL; const int N = 10005; const LL MOD = 1000000007; bool prime[N]; int p[N]; int k; vector<LL> v1; vector<LL> v2; vector<LL> *p1; vector<LL> *p2; void isprime() { k = 0; int i,j; memset(prime,true,sizeof(prime)); for(i=2;i<N;i++) { if(prime[i]) { p[k++] = i; for(j=i+i;j<N;j+=i) { prime[j] = false; } } } } void Work() { p1 = &v1; p2 = &v2; for(int i=0;i<N;i++) { if(i&1) p1->push_back(0); else p1->push_back(1); } for(int i=1;i<k;i++) { p2->clear(); for(int j=0;j<N;j++) { if(j < p[i]) p2->push_back((*p1)[j]%MOD); else p2->push_back(((*p1)[j]%MOD + (*p2)[j-p[i]]%MOD)%MOD); } vector<LL> *tmp; tmp = p2; p2 = p1; p1 = tmp; } } int main() { int n; isprime(); Work(); while(cin>>n) { cout<<(*p1)[n]<<endl; } return 0; }