首页 > 代码库 > P2563 [AHOI2001]质数和分解
P2563 [AHOI2001]质数和分解
题目描述
任何大于 1 的自然数 n 都可以写成若干个大于等于 2 且小于等于 n 的质数之和表达式(包括只有一个数构成的和表达式的情况)，并且可能有不止一种质数和的形式。例如，9 的质数和表达式就有四种本质不同的形式：
9 = 2 + 5 + 2 = 2 + 3 + 2 + 2 = 3 + 3 + 3 = 2 + 7 。
这里所谓两个本质相同的表达式是指可以通过交换其中一个表达式中参加和运算的各个数的位置而直接得到另一个表达式。
试编程求解自然数 n 可以写成多少种本质不同的质数和表达式。
输入输出格式
输入格式：
文件中的每一行存放一个自然数 n(2 < n < 200) 。
输出格式：
依次输出每一个自然数 n 的本质不同的质数和表达式的数目。
输入输出样例
输入样例#1：
2200
输出样例#1：
19845164
先生成一个质数表然后用个小背包就可以了
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 #define lli long long int 7 using namespace std; 8 void read(lli &n) 9 {10 char c=‘+‘;lli x=0;bool flag=0;11 while(c<‘0‘||c>‘9‘)12 {c=getchar();if(c==‘-‘)flag=1;}13 while(c>=‘0‘&&c<=‘9‘)14 {x=x*10+(c-48);c=getchar();}15 flag==1?n=-x:n=x;16 }17 lli n,m;18 lli a[10001];19 lli dp[10001];20 lli sum[10001];21 lli vis[10001];22 int main()23 {24 dp[0]=1;25 vis[1]=1;26 for(lli i=2;i<=201;i++)27 if(!vis[i])28 for(lli j=i*i;j<=301;j+=i)29 vis[j]=1;30 for(lli i=2;i<=200;i++)31 if(vis[i]==0)32 for(lli j=i;j<=200;j++)33 dp[j]=dp[j-i]+dp[j];34 while(scanf("%d",&n)==1)35 {36 printf("%lld\n",dp[n]);37 }38 return 0;39 }
P2563 [AHOI2001]质数和分解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。