首页 > 代码库 > 洛谷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
动态规划。
可以先打出素数表，然后做类似完全背包的DP，方程：f[x]+=f[x-pri[i]] 1<=x<=200
数据范围很小，DP打出答案表以后依次回答询问即可。
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 const int mxn=300; 9 int pri[mxn],cnt=0;10 bool vis[mxn];11 void Pri(){12 int i,j;13 for(i=2;i<mxn;i++){14 if(!vis[i]){pri[++cnt]=i;}15 for(j=1;j<=cnt && pri[j]*i<mxn;j++){16 vis[pri[j]*i]=1;17 if(i*pri[j]==0)break;18 }19 }20 return;21 }22 int n;23 int f[mxn];24 int main(){25 Pri();26 int i,j;27 memset(f,0,sizeof f);28 f[0]=1;29 for(i=1;i<=cnt;i++){30 for(j=pri[i];j<mxn;++j){31 f[j]+=f[j-pri[i]];32 }33 }34 while(scanf("%d",&n)!=EOF){35 printf("%d\n",f[n]);36 }37 return 0;38 }
洛谷P2563 [AHOI2001]质数和分解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。