思路

要把 $n$ 分解成尽可能多的、大于 $1$ 的奇数之和。

设分成 $k$ 段。每段都是大于 $1$ 的奇数，最小为 $3$，所以 $n\ge3k$，即 $k\le\lfloor n/3\rfloor$；又因为 $k$ 个奇数之和与 $k$ 同奇偶，所以 $k\equiv n\pmod2$。

于是最大段数 $q$：

• $n\%3=0$：$q=n/3$，用 $n/3$ 个 $3$；
• $n\%3=2$：$q=\lfloor n/3\rfloor$，用 $\lfloor n/3\rfloor-1$ 个 $3$ 和一个 $5$；
• $n\%3=1$：$k=\lfloor n/3\rfloor$ 与 $n$ 奇偶性不同（相差 $1$），取不到，最大只能是 $q=\lfloor n/3\rfloor-1$；构造上把两个 $3$ 和一个 $1$ 合成一个 $7$：用 $\lfloor n/3\rfloor-2$ 个 $3$ 和一个 $7$（$n=7$ 时就是单独一个 $7$），恰好 $q$ 段。

$n=1,2,4$ 无解：它们无法写成大于 $1$ 的奇数之和（$4$ 只能写成 $3+1$，而 $1$ 不合法）。

每组 $O(1)$ 计算，总复杂度 $O(t)$，空间复杂度 $O(1)$。

代码

#include <iostream>

using namespace std;

int main()
{
    int t; cin >> t;          // 测试数据组数
    while(t--)
    {
        long long n; cin >> n;
        if(n == 1 || n == 2 || n == 4)// 这三种情况无法拆分，无解
        {
            cout << -1 << endl;
        }
        else
        {
            int k = n % 3;
            if(k == 0 || k == 2) cout << n / 3 << endl;   // 余 0：全用 3；余 2：把最后的 2 并成 5
            else cout << n / 3 - 1 << endl;               // 余 1：少用一个 3，与 1 合成 7
        }
    }
    return 0;
}