c++求解神奇阵法求解

Question

神奇阵法

在古老的大地上，有一种神奇的阵法。这种阵法有四个阵眼，分布在东南西北四个方位，每个方位上可以各自嵌入一个特征值。有一天，一个英雄少年手持一个写有一个数字 n 的宝器来到这片大地，他要在四个阵眼上分别打入一个特征值，如果这些特征值满足以下条件，就能开启阵法：

每个特征值是大于1的正整数，除了1和它本身以外不再有其他因数。
四个特征值之和是 n。
英雄少年好奇总共有多少种安放特征值的方法，能够开启这个神奇阵法。请你帮他计算一下吧。

输入描述

第一行输入正整数 T，表示有 T 组数据。

以下输入 T 行，每行输入一个正整数 n，含义如题面所述。

输出描述

输出 T 行，每行表示能够开启神奇阵法的特征值安放方案数。

用例输入 1

2
9
10
用例输出 1

4
6

数据范围
对于 100% 的数据， T≤10。

对于 10% 的数据，n≤10。

对于 40% 的数据，n≤100。

对于 70% 的数据，n≤1000。

对于 100% 的数据，n≤100000。

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

要解决这个问题，我们可以采用递归搜索的方法，但这种方法在数据量较大时效率会很低。考虑到数据范围，我们可以采用一种更高效的算法，即动态规划。

首先，我们需要理解问题的本质：我们需要找到所有四个质数的组合，它们的和等于给定的数字 n。这个问题可以转化为一个组合问题，即从 n 个数字中选择 4 个质数。

我们可以定义一个函数 countPrimes，它接受一个整数 n 作为参数，并返回小于或等于 n 的质数的数量。我们可以使用埃拉托斯特尼筛法（Sieve of Eratosthenes）来高效地生成质数。

接下来，我们可以定义一个动态规划数组 dp，其中 dp[i] 表示和为 i 的四个质数组合的数量。初始化时，dp[0] = 1（因为和为 0 的组合有一种，即选择空集），其他 dp[i] = 0。

然后，我们可以遍历所有小于或等于 n 的质数 p，对于每个质数，我们更新 dp[p] 到 dp[n-p] 的值。如果 dp[i-p] 不为 0，那么 dp[i] += dp[i-p]。

最后，输出 dp[n] 就是我们需要的解。

以下是 C++ 代码实现的示例：

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 100001;

// 埃拉托斯特尼筛法生成质数
vector<int> sievePrimes(int n) {
    vector<bool> isPrime(n+1, true);
    vector<int> primes;
    for (int p = 2; p <= n; ++p) {
        if (isPrime[p]) {
            primes.push_back(p);
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }
    return primes;
}

// 计算和为 n 的四个质数组合的数量
int countCombinations(int n, const vector<int>& primes) {
    vector<int> dp(n+1, 0);
    dp[0] = 1; // 和为 0 的组合有一种

    for (int p : primes) {
        if (p > n) break; // 质数大于 n 时停止
        for (int i = p; i <= n; ++i) {
            dp[i] += dp[i - p];
        }
    }

    return dp[n];
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> primes = sievePrimes(n);
        cout << countCombinations(n, primes) << endl;
    }
    return 0;
}

请注意，这段代码只是一个示例，可能需要根据实际问题进行调整。例如，如果 n 非常大，可能需要考虑内存优化或更高效的算法。

至于参考资料，你可以查看以下链接来了解更多关于埃拉托斯特尼筛法和动态规划的信息：

• 埃拉托斯特尼筛法
• 动态规划

希望这能帮助你解决问题！如果有其他问题或需要进一步的帮助，请随时告诉我。