P1832 A+B Problem(再升级)
2018-06-17 22:23:47来源:未知 阅读 ()
题目背景
·题目名称是吸引你点进来的
·实际上该题还是很水的
题目描述
·1+1=? 显然是2
·a+b=? 1001回看不谢
·哥德巴赫猜想 似乎已呈泛滥趋势
·以上纯属个人吐槽
·给定一个正整数n,求将其分解成若干个素数之和的方案总数。
输入输出格式
输入格式:一行:一个正整数n
输出格式:一行:一个整数表示方案总数
输入输出样例
7
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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:1191 数轴染色
- PTA 1002 A+B for Polynomials 2020-04-24
- 哈尔滨网络热身赛 2019-11-25
- 两个数的差 2019-10-16
- 又是a+b 2019-09-08
- a+b的问题 2019-09-08
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash