题目描述
难度分:$1300$
输入$T(\leq 10^5)$表示$T$组数据。每组数据输入$n(1 \leq n \leq 10^9)$。
把$n$表示成尽量多的合数之和。例如$12 = 4 + 4 + 4$。
输出合数的个数。如果无法做到,输出$-1$。
注:合数为大于$1$的非质数。
输入样例$1$
1
12
输出样例$1$
3
输入样例$2$
2
6
8
输出样例$2$
1
2
输入样例$3$
3
1
2
3
输出样例$3$
-1
-1
-1
算法
分类讨论
$4$是最小的合数,因此尽可能用更多的$4$来凑,分为以下几种情况:
- 如果$n$能够被$4$整除,那么就能分出$\frac{n}{4}$个$4$,这是最优解。
- 如果$n$除以$4$余$2$,那么最后这个$2$就合并到一个$4$中变成$6$,答案是$\lfloor \frac{n}{4} \rfloor$。
- 如果$n$除以$4$余$1$,可以枚举一下,在小于$13$的整数中,只有$9$的答案是$1$,其他的数都无法拆分成合数之和。而大于等于$13$的整数中,可以先分离出来一个$13$,变成$13=4+9$两个合数之和,剩下的部分一定可以被$4$整除,答案为$\frac{n-13}{4}+2$。
- 如果$n$除以$4$余$3$,可以枚举一下,小于$15$的整数都不可能拆分成整数之和。而大于等于$15$的整数中,可以先分离出一个$15$,变成$15=6+9$两个合数之和,剩下的部分一定可以被$4$整除,答案为$\frac{n-15}{4}+2$。
- 最后就是$n$小于$4$的情况,$1$是个非质数非合数,$2$和$3$都是质数,拆不出两个合数之和,这种情况肯定无解。
复杂度分析
时间复杂度
根据$n$除以$4$的余数,进行分类讨论,进行一个整数除法就能得到答案,时间复杂度为$O(1)$。
空间复杂度
只使用了有限几个变量,算法的额外空间复杂度为$O(1)$。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int t, n;
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
if(n < 4) {
puts("-1");
}else {
if((n % 4) % 2 == 0) {
printf("%d\n", n / 4);
}else {
if(n % 4 == 1) {
if(n < 13) {
if(n == 9) puts("1");
else puts("-1");
}else {
printf("%d\n", (n - 13) / 4 + 2);
}
}else {
if(n < 15) {
puts("-1");
}else {
printf("%d\n", (n - 15) / 4 + 2);
}
}
}
}
}
return 0;
}