题面
【问题描述】
将 2019 拆分为若干个两两不同的质数之和，一共有多少种不同的方法？
注意交换顺序视为同一种方法，例如 2 + 2017 = 2019 与 2017 + 2 = 2019 视为同一种方法。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
思路
完全背包问题。
题意为，给你一堆物品，重量都为2019以内的质数，且每个重量的物品有无限多个，问能有多少种方案能恰好填满重量为2019的背包。
先用欧式筛晒出 1 ~ 2019 以内的质数，再套完全背包的板子即可。注意使用 long long，不然要爆。
令 表示前 i 种物品中恰好装满质量为 j 的背包的方案数，其状态转移方程如下（p[i]为第 i 个质数）：
还可以优化为一维的背包，但是填空题没必要。
答案：55965365465060
代码
#include<iostream>
using namespace std;
typedef long long LL;
const int M = 2030;
bool v[M];
int prime[M], tot;
LL f[M][M];
void pre() {
for (int i = 2; i < M; ++i) {
if (!v[i]) {
prime[++tot] = i;
for (int j = 2; j * i < M; ++j) v[j * i] = true;
}
}
}
int main() {
pre();
f[0][0] = 1; //边界情况
for (int i = 1; i <= tot; ++i) { //遍历每个质数
for (int j = 0; j <= 2019; ++j) { //遍历每种背包质量的情况
f[i][j] = f[i - 1][j];
if (j >= prime[i]) f[i][j] += f[i - 1][j - prime[i]];
}
}
cout << f[tot][2019] << endl;
return 0;
}
| 标题： | 2019第十届蓝桥杯国赛-B质数拆分 |
|---|---|
| 链接： | https://www.fightingok.cn/detail/113 |
| 更新： | 2022-09-18 22:39:57 |
| 版权： | 本文采用 CC BY-NC-SA 3.0 CN 协议进行许可 |