【CSP-S膜你考】 A
2019-10-17 08:57:51来源:博客园 阅读 ()
【CSP-S膜你考】 A
A
题面
对于给定的一个正整数n, 判断n是否能分成若干个正整数之和 (可以重复) ,
其中每个正整数都能表示成两个质数乘积。
输入格式
第一行一个正整数 q,表示询问组数。
接下来 q 行,每行一个正整数 n,表示询问。
输出格式
q 行,每行一个正整数,为 0 或 1。0 表示不能,1 表示能。
样例
$\texttt{input#1}$
5
1
4
5
21
25
$\texttt{output#1}$
0
1
0
1
1
数据范围与提示
样例解释:
4 = 2 * 2
21 = 6 + 15 = 2 * 3+3 * 5
25 = 6 + 9 + 10 = 2 * 3+3 * 3+2 * 5
25 = 4 + 4 + 4 + 4 + 9 = 2 * 2+2 * 2+2 * 2+2 * 2+3 * 3
30%的数据满足:q<=20,n<=20
60%的数据满足:q<=10000,n<=5000
100%的数据满足:q<=10^5,n<=10^18
题解
4x + 6y 可以凑出大于等于4的全部偶数,又因为4x + 6y 可以拆成x个2 * 2及y个2 * 3相加。所以大于等于4的偶数全部可拆。大于等于13的奇数完全可以表示成大于等于4的偶数加9,大于等于4的偶数全部可拆,9也可拆,所以大于等于13的奇数也可拆。小于等于12的数中4,6,8,9,10,12是可拆的,0,1,2,3,5,7,11是不可拆的。所以大于等于12的全可拆,小于12的只有4,6,8,9,10可拆。
$Code$
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
typedef long long ll;
ll q,n;
inline void read(ll &T) {
ll x=0;bool f=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
T=f?-x:x;
}
int main() {
read(q);
while(q--) {
read(n);
if(n>=12) puts("1");
else {
if(n==4||n==6||n==8||n==9||n==10) puts("1");
else puts("0");
}
}
return 0;
}
原文链接:https://www.cnblogs.com/poi-bolg-poi/p/11685758.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:C++构造和解析JSON
- 【CSP-S膜你考】那23个路口 2019-10-25
- 【CSP-S膜你考】即时战略(模拟) 2019-10-17
- 【CSP-S膜你考】最近公共祖先 To Be Continued 2019-10-12
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