codeforces 870C
2 seconds
256 megabytes
standard input
standard output
You are given several queries. In the i-th query you are given a single positive integer ni. You are to represent ni as a sum of maximum possible number of composite summands and print this maximum number, or print -1, if there are no such splittings.
An integer greater than 1 is composite, if it is not prime, i.e. if it has positive divisors not equal to 1 and the integer itself.
The first line contains single integer q (1 ≤ q ≤ 105) — the number of queries.
q lines follow. The (i + 1)-th line contains single integer ni (1 ≤ ni ≤ 109) — the i-th query.
For each query print the maximum possible number of summands in a valid splitting to composite summands, or -1, if there are no such splittings.
1
12
3
2
6
8
1
2
3
1
2
3
-1
-1
-1
12 = 4 + 4 + 4 = 4 + 8 = 6 + 6 = 12, but the first splitting has the maximum possible number of summands.
8 = 4 + 4, 6 can't be split into several composite summands.
1, 2, 3 are less than any composite number, so they do not have valid splittings.
说出来你们可能不信。。这题到最后我也没读懂啥意思(composite是合数的意思。。
满脑子想的是筛法,没想到就是考个思维。。。
题意:给一个数,问这个数最多能由多少个合数组成,不能组成就输出-1.
解题思路:因为最小的合数是4,所以如果n正好是4的倍数就是最多的情况。
那么就可以想到考虑n%4的情况。
1.n%4==0 这个时候直接输出n/4即可。
2.n%4==2 这个时候还是直接输出n/4,因为n%4==2相当于(n-6)%4==0,而6也是合数。
3.n%4==1 || n%4==3 那么n自然是个奇数,这个时候我们找个最小的奇合数处理下就行(n-=9;
此时n就是个偶数了,如果n!=0 && n<4 ,那么这个数就没法全由合数构成。
反之,则能构成,ans=1+n/4;
ac代码:
1 #include <cstdio>
2 #include <iostream>
3 using namespace std;
4 int main() {
5 ios::sync_with_stdio(false);
6 cin.tie(0);cout.tie(0);
7 int q,n;
8 cin>>q;
9 while(q--) {
10 cin>>n;
11 int ans=0;
12 if(n%4==0||n%4==2) {
13 ans=n/4;
14 }
15 else if(n%4==1 ||n%4==3) {
16 n-=9;
17 ans=n/4+1;
18 }
19 if(n<4 && n!=0) ans=-1;
20 cout<<ans<<endl;
21 }
22 return 0;
23 }
最新文章
- 在PHP语言中使用JSON和将json还原成数组
- vs签入签出--TFS进行源代码管理
- ECMAScript 位运算符
- 漫谈Java虚拟机(JVM)
- bzoj2749
- 求LR(0)文法的规范族集和ACTION表、GOTO表的构造算法
- Linux下的I/O模型以及各自的优缺点
- Nastya Is Buying Lunch
- socket跟TCP/IP 的关系,单台服务器上的并发TCP连接数可以有多少
- Java接口自动化测试之集成MyBatis和MySQL (五)
- linux 通过pid 寻找程序路径的最简单命令(pwdx)
- openssl签署和自签署证书的多种实现方式
- python3 独立环境 virtualenv &; conda
- topcoder srm 510 div1
- (转)php语法(符号用法)
- IOS 学习 Key-value coding
- 获取List对象的泛型类(原创)
- Web App, Native APP,Hybird App 介绍
- RedisTemplate和StringRedisTemplate
- js 时间date格式化