·题目名称是吸引你点进来的
·实际上该题还是很水的
·1+1=? 显然是2
·a+b=? 1001回看不谢
·哥德巴赫猜想 似乎已呈泛滥趋势
·以上纯属个人吐槽
·给定一个正整数n,求将其分解成若干个素数之和的方案总数。
输入格式:
一行:一个正整数n
输出格式:
一行:一个整数表示方案总数
输入样例#1:
7
输出样例#1:
3
【样例解释】
7=7 7=2+5
7=2+2+3
【福利数据】
【输入】 20
【输出】 26
【数据范围及约定】
对于30%的数据 1<=n<=10
对于100%的数据,1<=n<=10^3
生成一个素数表,
然后暴力求解
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #define lli long long int
6 using namespace std;
7 const int MAXN=100001;
8 lli vis[MAXN];
9 lli dp[MAXN];
10 int main()
11 {
12 lli n,q;
13 cin>>n;
14 dp[0]=1;
15 vis[1]=1;
16 for(lli i=2;i<=sqrt(n);i++)
17 {
18 if(vis[i]==0)
19 for(lli j=i*i;j<=n;j=j+i)
20 vis[j]=1;
21 }
22 for(lli i=2;i<=n;i++)
23 if(vis[i]==0)
24 for(lli j=i;j<=n;j++)
25 dp[j]+=dp[j-i];
26 cout<<dp[n];
27 return 0;
28 }