「SCOI 2009」游戏

题目大意：

问题相当于求 $x_1+x_2+\cdots x_r \leq n$ 的解的个数，之所以是 $\leq$ 是因为可以补 $1$，其中 $x_i=p_i^{a_i}$，$p_i$ 是质数。

01背包问题，注意 $i,j,k$ 的枚举顺序。

#include <cstdio>

const int N = 1005;
int np[N], p[N], q[N][N], n, m; long long f[N] = {1}, ans;

void prime(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!np[i]) p[++m] = i;
        for (int j = 1; j <= m && i * p[j] <= n; ++j) {
            np[i*p[j]] = 1;
            if (i % p[j] == 0) break;
        }
    }
}

int main() {
    scanf("%d", &n);
    prime(n);
    for (int i = 1; i <= m; ++i)
        for (int j = 1, k = p[i]; k <= n; ++j, k *= p[i])
            q[i][j] = k;
    for (int i = 1; i <= m; ++i) //前i个质数
        for (int j = n; j >= 2; --j) //和为j
            for (int k = 1; q[i][k] && q[i][k] <= j; ++k) //第i个质数的指数
                f[j] += f[j-q[i][k]];
    for (int i = 2; i <= n; ++i) ans += f[i];
    printf("%lld\n", ans + 1);
    return 0;
}