每个素数就是一个物品,然后就相当于求完全背包方案数
把max改成+就好了。
#include<cstdio>
#include<vector>
#include<cstring>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;typedef long long ll;
const int MAXN = 1123;
bool is_prime[MAXN];
vector<int> prime;
ll f[MAXN];void get_prime()
{memset(is_prime, true, sizeof(is_prime));is_prime[0] = is_prime[1] = false;REP(i, 2, MAXN){if(is_prime[i]) prime.push_back(i);REP(j, 0, prime.size()) //这里没有else,一定要做 {if(i * prime[j] > MAXN) break;is_prime[i * prime[j]] = false;if(i % prime[j] == 0) break;}}
}int main()
{get_prime();int n;scanf("%d", &n);f[0] = 1;REP(i, 0, prime.size()){int cur = prime[i];if(cur > n) break;REP(j, cur, n + 1)f[j] += f[j-cur];}printf("%lld\n", f[n]);return 0;
}