题目描述

难度分:$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$来凑，分为以下几种情况：

1. 如果$n$能够被$4$整除，那么就能分出$\frac{n}{4}$个$4$，这是最优解。
2. 如果$n$除以$4$余$2$，那么最后这个$2$就合并到一个$4$中变成$6$，答案是$\lfloor \frac{n}{4} \rfloor$。
3. 如果$n$除以$4$余$1$，可以枚举一下，在小于$13$的整数中，只有$9$的答案是$1$，其他的数都无法拆分成合数之和。而大于等于$13$的整数中，可以先分离出来一个$13$，变成$13=4+9$两个合数之和，剩下的部分一定可以被$4$整除，答案为$\frac{n-13}{4}+2$。
4. 如果$n$除以$4$余$3$，可以枚举一下，小于$15$的整数都不可能拆分成整数之和。而大于等于$15$的整数中，可以先分离出一个$15$，变成$15=6+9$两个合数之和，剩下的部分一定可以被$4$整除，答案为$\frac{n-15}{4}+2$。
5. 最后就是$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;
}