67要拿🏀杯国一，你们知道吗？

结论

• 若 $n = 1$ 或 $n$ 是质数，答案为 $1$
• 若 $n$ 是合数，答案为 $\lfloor n/2 \rfloor$

分析

1. $n = 1$

无法进行任何拆分，直接返回 $1$。

2. $n$ 是质数

假设存在拆分 $n = y + z$ 且 $\gcd(y, z) > 1$。设 $d = \gcd(y, z) > 1$，则 $y = d \cdot a$，$z = d \cdot b$，且 $a + b = n/d$。因为 $n$ 是质数且 $d > 1$，所以 $d = n$，于是 $a + b = 1$，与 $a, b \ge 1$ 矛盾。因此质数无法拆分。

3. $n$ 是合数（$n \ge 4$）

偶数合数：设 $n = 2k$。每次拆出 $2$：$2k \to 2 + (2k-2)$，$\gcd(2, 2k-2) = 2 > 1$。最终得到 $k$ 个 $2$，答案为 $n/2$。

奇数合数：设 $n = 2k+1$ 且 $n \ge 9$。目标是构造 $1$ 个 $3$ 和 $k-1$ 个 $2$。

• 如果 $n$ 是 $3$ 的倍数，拆 $n = 3 + (n-3)$，$n-3$ 是偶数全拆成 $2$。

• 否则设 $p$ 是 $n$ 的最小奇质因子（$n = p \cdot m$，$p \ge 5$），拆 $n = 3p + p(m-3)$：

  • $3p$ 是 $3$ 的倍数，拆成 $3$ + 一堆 $2$
  • $p(m-3)$ 中 $m-3$ 是偶数，所以这部分全是偶数，全拆成 $2$

举例（$n = 49$）：

$49 = 7 \times 7$，不是 $3$ 的倍数，最小奇质因子 $p = 7$，$m = 7$。

第一步：$49 = 3 \times 7 + 7 \times (7-3) = 21 + 28$

• $21$ 是 $3$ 的倍数：$21 = 3 + 18$，$18$ 是偶数 → $9$ 个 $2$，加上 $1$ 个 $3$，共 $10$ 个元素
• $28$ 是偶数：全拆成 $14$ 个 $2$

最终：$1$ 个 $3$ + $9$ 个 $2$ + $14$ 个 $2$ = $24$ 个元素 = $\lfloor 49/2 \rfloor$ ✓

最终答案为 $\lfloor n/2 \rfloor$。

代码

#include <bits/stdc++.h>
using namespace std;

vector<int> sieve_primes(int limit) {
    vector<bool> is_prime(limit + 1, true);
    vector<int> primes;
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= limit; ++i) {
        if (is_prime[i]) primes.push_back(i);
        for (int p : primes) {
            if (1LL * i * p > limit) break;
            is_prime[i * p] = false;
            if (i % p == 0) break;
        }
    }
    return primes;
}

bool is_prime(int n, const vector<int>& primes) {
    if (n < 2) return false;
    for (int p : primes) {
        if (1LL * p * p > n) break;
        if (n % p == 0) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    vector<int> primes = sieve_primes(31623);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        if (n == 1) cout << 1 << '\n';
        else if (is_prime(n, primes)) cout << 1 << '\n';
        else cout << n / 2 << '\n';
    }
    return 0;
}