求两两不同的素数组成2019的方案数
注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
结果: 55965365465060
代码:
#include
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;
bool vis[12345];
vectorprime;
ll f[3000][3000];
void init() { //素数筛
for(int i = 2;
i<= 3000;
i++) {
if(!vis[i]) {
for(int j = i*i;
j<= 3000;
j+= i) {
vis[j] = true;
}
}
}
for(int i = 2;
i<= 2019;
i++) {
if(!vis[i]) prime.push_back(i);
}
}ll dfs(int pos,int sum) {
if(f[pos][sum]!= -1) return f[pos][sum];
if(sum == 2019) return 1;
if(pos>= prime.size()||sum> 2019) return 0;
ll ans = 0;
ans+= dfs(pos+1,sum);
// 不要当前这个素数
ans+= dfs(pos+1,sum+prime[pos]);
// 要当前这个素数
return f[pos][sum] = ans;
}int main() {
init();
mem(f,-1);
ll ans = dfs(0,0);
cout< 【蓝桥杯|2019第十届蓝桥杯B组决赛题解第二题】
推荐阅读
- 算法与数据结构|第十届蓝桥杯大赛软件类省赛Java研究生组-题解
- 蓝桥杯|第十届蓝桥杯省赛编程题题解（C++A组）
- 蓝桥杯|第八届蓝桥杯省赛代码+题解
- 蓝桥杯|第九届蓝桥杯省赛代码+题解
- C语言程序练习|交换最小值和最大值
- 蓝桥杯单片机|蓝桥杯单片机之PCF8591模块的使用
- 蓝桥杯模块|蓝桥杯单片机模块代码（PCF8591）(代码+注释)
- 蓝桥杯单片机|蓝桥杯单片机 | 特训案例【进阶04】24C02存储按键触发次数
- 蓝桥杯单片机|蓝桥杯单片机 | 特训案例【进阶05】采样光敏电阻与可调电阻的电压