质数拆分
题目 质数拆分
思路分析
注意不是只拆成a+b 若a中还能拆出c和d要继续去拆
最开始写成了 拆分成ab俩 但是发现只有2，2017这一对
尝试对这一对进行dfs
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 100010;
bool isnot_prime[N];
set<int> primes;
int cnt = 0;
void get_primes(int n) {
for (int i = 2; i <= n; i++) {
if (!isnot_prime[i]) {
primes.insert(i);
for (int j = i * 2; j <= n; j += i) {
isnot_prime[j] = true;
}
}
}
}
void dfs(set<int>::iterator it, set<int>::iterator end, int a, int b) {
if (a == 0 && b == 0) {
cnt++;
return;
}
for (auto i = it; i != end; i++) {
int x = *i;
if (a >= x) dfs(next(i), end, a - x, b);
if (b >= x) dfs(next(i), end, a, b - x);
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
get_primes(2019);
dfs(primes.begin(), primes.end(), 2, 2017);
cout << cnt / 2 << endl;
return 0;
}
- 用一个从当前质数开始的迭代器，递归时只考虑这个迭代器之后的质数，以避免重复。
- 通过 next(i) 确保在递归时不会重复考虑相同的质数组合。
- 终止条件是当 a 和 b 同时为0时，这意味着找到了一种有效的组合方式。
- 由于每种组合可能会被计算两次（对于a和b的顺序），结果需要除以2。
在 C++ 中，使用 next(i) 是一种从给定迭代器（这里是 i）开始，向前移动一位的操作。这个函数属于
在您的 dfs 函数中，使用 next(i) 有两个主要目的：
- 避免重复组合：通过从当前质数的下一个开始递归调用 dfs，确保每次递归考虑的质数集合都是减少的。这意味着对于每个质数，我们只考虑它之后的质数组合，从而避免了重复计算相同的组合。例如，如果质数集合是 {2, 3, 5, 7}，在考虑 2 时，接下来只考虑 {3, 5, 7} 而不再重新考虑 2。
- 防止无限递归：如果不使用 next(i)，则递归调用可能会不断重复相同的迭代器位置，导致无限递归。例如，如果我们继续用相同的 i 调用 dfs，则 dfs 函数可能会不停地尝试将同一个数 x 从 a 或 b 中减去，从而永远不会到达终止条件（a 0 && b 0）。
这里是具体的代码片段解释，展示了 next(i) 如何工作：
for (auto i = it; i != end; i++) {
int x = *i;
if (a >= x) dfs(next(i), end, a - x, b); // 只考虑当前质数之后的质数来减少a
if (b >= x) dfs(next(i), end, a, b - x); // 只考虑当前质数之后的质数来减少b
}
这样，每次递归调用都是从质数集合的一个更小的子集开始，减少计算量，避免重复，并尝试所有可能的组合。
但是效率太低了 运行结果半天出不来
考虑换dp写
发现其实是背包问题
从前i个数里面选 总价值恰好等于2019的所有选法的集合 属性count
状态：f[i][j]表示选到第i个数且当前体积是j的方案数
转移方程：
f[i][j]+=f[i-1][j]不选第i个数
if(j>=prime[i])
f[i][j]+=f[i-1][j-prime[i]]选第i个数
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const int N=10010;
bool st[N];
int primes[N],cnt=1;
LL f[N][N];
void get_primes(int n){
for(int i=2;i<=n;i++){
if(!st[i]){
primes[cnt++]=i;
for(int j=i;j<=n;j+=i)
st[j]=true;
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
get_primes(2019);
int n=cnt-1,m=2019;
f[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
f[i][j]+=f[i-1][j];
if(j>=primes[i])
f[i][j]+=f[i-1][j-primes[i]];
}
}
cout<<f[n][m];
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const int N=10010;
bool st[N];
int primes[N],cnt=1;
LL f[N];
void get_primes(int n){
for(int i=2;i<=n;i++){
if(!st[i]){
primes[cnt++]=i;
for(int j=i;j<=n;j+=i)
st[j]=true;
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
get_primes(2019);
int n=cnt-1,m=2019;
f[0]=1;
for(int i=1;i<=n;i++){
for(int j=m;j>=primes[i];j--){
f[j]=f[j]+f[j-primes[i]];
}
}
cout<<f[m];
return 0;
}
💬 评论