題目： 2019可以被分解成若干個兩兩不同的素數，請問不同的分解方案有多少種？

注意：分解方案不考慮順序，如2+2017=2019和2017+2=2019屬于同一種方案。

思路先求出2019內的所有素數時間復雜度O(n)(求質素用的歐拉線性篩法，這部分不理解前面有寫https://www.jianshu.com/p/ef57c98c0e4e)

再dfs爆索，中間記得剪枝

#include

#define mem(kk,int) memset(kk,int,sizeof kk);

using namespace std;

typedef long long ll;

vectorprime;//這里寫int prime[];也可

bool vis[4000];

ll f[4000][4000];

void init(){//求素數，放入prime里面

for(int i=2;i<=2019;i++){

if(!vis[i])prime.push_back(i);

for(int j=0;i*prime[j]<=2019&&j

vis[i*prime[j]]=true;

if(i%prime[j]==0)break;

}

}

}

ll dfs(ll num,ll sum){

if(f[num][sum]!=-1)return f[num][sum];

if(sum==2019)return 1;

if(num>=prime.size()||sum>2019)return 0;

ll ans=0;

ans+=dfs(num+1,sum);//選

ans+=dfs(num+1,sum+prime[num]);//不選

return f[num][sum]=ans;

}

int main(){

init();

/*for(int i=0;i

cout<

cout<

mem(f,-1);

ll ans=dfs(0,0);

cout<

return 0;

}

總結

以上是生活随笔為你收集整理的第十届蓝桥杯c语言b组试题,2019年第十届蓝桥杯（决赛）国赛B组C++（B）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。