[2022.1.13]UPC-2021级新生个人训练赛第22场-10151 Problem D 连续质数和
2022/1/13 23:34:16
本文主要是介绍[2022.1.13]UPC-2021级新生个人训练赛第22场-10151 Problem D 连续质数和,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
问题 D: 连续质数和
时间限制: 1.000 Sec 内存限制: 128 M
题目描述
质数又称素数,是大于 1 的正整数,除了 1 和它本身外不能被其他自然数整除,有无限 个,比如,2、3、5、7 等都是质数,但比如 9 就不是质数,因为它除了能被 1 和它自己整 除外,还能被 3 整除。
悦悦小朋友对这类质数非常感兴趣,因为他发现有一些数是能通过连续的质数相加得 到的。比如 5+ 7 + 11 + 13 + 17=53,也就是整数 53 可以由连续的质数 5、7、11、13、17 相 加得到。有时相加的方案还不止一种,比如整数 41 就有 3 种不同的连续质数相加方案:
2+3+5+7+11+13=41,11+13+17=41,还有一种就它本身,即 41=41。但也有的数是没有这样
相加方案的,比如整数 20 就找不到连续质数相加的方案,虽然 7 + 13 或者 3 + 5 + 5 + 7 的 结果都是 20,但前者没有连续,后者质数被重复相加了 。悦悦在纸上写了 N(1≤N≤100000) 个数,他想知道每一个整数 Mi(2≤Mi≤100000,1≤i≤N)到底有多少种连续质数相加的 方案?请你编程帮助他一下吧。
输入
输入共 N+1 行。 第 1 行一个整数 N,表示悦悦在纸上写了 N 个整数。
接下来每行一个整数,其中第 i+1 行表示整数 Mi
输出
输出共 N 行。 输出的第 i 行表示整数 Mi 有多少种连续质数相加的方案。
样例输入
4 2 12 17 20
样例输出
1 1 2 0
提示
样例中悦悦写了4个整数,分别为2,12,17和20。因为2=2,所以2可以找到满足条件的1种方案。
因为5+7=12,所以12有1种方案。
因为2+3+5+7=17,17=17,所以17有2种方案满足条件。
20没有满足条件的方案,所以输出0。
对于30%的数据保证1≤N≤100,2≤Mi≤100。对于50%的数据保证1≤N≤1000,2≤Mi≤1000。
对于100%的数据保证1≤N≤100000,2≤Mi≤100000。
想法:
其实.....好像问题并不是很困难,先用素数筛筛选出1000000以内的素数,然后利用前缀和来计算连续素数和就可以过啦。
但是好多人都时间超限了......这道题在代码实现的过程中要十分注意优化...
让我们来看代码吧?
#include <cstdio> #define MX 1e9 #define MN -1e9 typedef long long int ll; using namespace std; int pri[10000]; int bet[10000]; bool isp[100010]; ll cnt; inline ll solve(ll tar){ //这是求解过程 ll i=0,j=0,tol=0; //其实不用写成函数,直接复制下去就可以。 do{ j++; while(bet[j]-bet[i]>tar) //这里只用了一层循环,比两层循环的会快一些! i++; //很多求子列的问题都可以用一层循环完成。 if(bet[j]-bet[i]==tar) //那些的问题的共同特点是: tol++; //如果当前子列不满足条件,相同起点的所有子列都不会满足。 }while(j>i); //也就是说...子列必须是有序的?。 return tol; } int main(){ ll i,j,n,tar; bet[cnt]+=pri[cnt]; for(i=2;i<=100010;i++){ //用埃氏筛筛选素数 if(isp[i]) continue; pri[++cnt]=i; bet[cnt]=pri[cnt]+bet[cnt-1]; for(j=i;j*i<=100010;j++){ isp[j*i]= true; } } scanf("%lld",&n); for(i=1;i<=n;i++){ scanf("%lld",&tar); printf("%lld\n",solve(tar)); } }
我把1也作为素数加进去了......结果错麻了,WA了一整晚.. : (
这篇关于[2022.1.13]UPC-2021级新生个人训练赛第22场-10151 Problem D 连续质数和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升