題目： UVa - 1213 - Sum of Different Primes

題目說明

給兩個整數 n、k，求將 n 拆為 k 個質數相加的結果有幾種。

Input： 每行兩個整數依序代表 n、k，若皆為 0 表結束。

Output： 輸出將 n 拆為 k 個質數相加的結果有幾種。

解題思路

因為 n <= 1120，所以先使用質數篩找出小於等於 1120 的所有質數。

定義 dp[i][j]，表將 i 拆為 j 個質數相加的情況數。

之後 DP，對於 dp[i][j] 來說，dp[i][j] += dp[i - v][j - 1]，對於所有 v 為小於等於 i 的質數。
可思考成 v 為最後加入的質數。

由於 DP 縮減了一維，所以計算時要從後面往前算。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>

using namespace std;

// reference: https://ppt.cc/fAybWx

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

int primeCnt;      // 質數個數
int primes[187];   // 只有 187 個質數
bool visited[1121];
int dp[1121][15];

// get all primes
void sieve()
{
    for (int i = 2; i <= 1120; ++i)
    {
        if (visited[i]) continue;
        primes[primeCnt++] = i;
        for (int j = i + i; j <= 1120; j += i) visited[j] = true;
    }
}

void compute()
{
    for (auto& v : primes) for (int i = 1120; i >= v; --i)
    {
        if (i == v) dp[v][1] = 1;
        for (int j = 2; j <= 14; ++j) dp[i][j] += dp[i - v][j - 1];
    }
}

void solve()
{
    int n, k;
    while (cin >> n >> k && n && k) cout << dp[n][k] << '\n';
}

int main()
{
   sieve();
   compute();
   solve();
}

參考資料

UVa 1213 - Sum of Different Primes_小白菜又菜-CSDN博客