今天做了一道有意思的题，于是乎，我写下了题解。。。。。
- 预处理质数：
- 使用埃拉托色尼筛法找出所有小于等于 ( 4 \times 10^7 ) 的质数。
- 将这些质数存储在一个数组中。
- 前缀和数组：
- 利用质数数组构建一个前缀和数组，其中每个元素表示从第一个质数开始累积到当前质数的和。
- 这样可以快速求出任意区间内连续质数的和。
- 查询处理：
- 对每个输入的 ( n )，通过前缀和数组查找连续质数和等于 ( n ) 的情况。
- 使用双重循环遍历前缀和数组，找出所有符合条件的区间。
下面是具体的代码实现：
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 40000000;
// 标记质数的数组
bool is_prime[MAX_N + 1];
// 存储所有质数
vector<int> primes;
// 前缀和数组
vector<long long> prefix_sum;
void sieve() {
fill(is_prime, is_prime + MAX_N + 1, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= MAX_N; i++) {
if (is_prime[i]) {
primes.push_back(i);
for (long long j = 1LL * i * i; j <= MAX_N; j += i) {
is_prime[j] = false;
}
}
}
}
void compute_prefix_sum() {
long long sum = 0;
for (int prime : primes) {
sum += prime;
prefix_sum.push_back(sum);
if (sum > MAX_N) break;
}
}
int count_ways(int n) {
int ways = 0;
for (int i = 0; i < prefix_sum.size(); i++) {
for (int j = i; j < prefix_sum.size(); j++) {
if (prefix_sum[j] - (i == 0 ? 0 : prefix_sum[i - 1]) == n) {
ways++;
} else if (prefix_sum[j] - (i == 0 ? 0 : prefix_sum[i - 1]) > n) {
break;
}
}
}
return ways;
}
int main() {
sieve();
compute_prefix_sum();
int T;
cin >> T;
vector<int> results;
while (T--) {
int n;
cin >> n;
results.push_back(count_ways(n));
}
for (int result : results) {
cout << result << endl;
}
return 0;
}
解释
- 埃拉托色尼筛法：
sieve函数用来筛选所有小于等于 ( 4 \times 10^7 ) 的质数，并将它们存储在primes向量中。
- 前缀和计算：
compute_prefix_sum函数构建质数的前缀和数组prefix_sum，每个元素表示从第一个质数到当前质数的累积和。
- 查询处理：
count_ways函数通过双重循环遍历prefix_sum数组，计算有多少种不同的表示形式使得连续质数的和等于给定的 ( n )。
- 主函数：
- 读取输入的 ( T ) 和每个 ( n )，并调用
count_ways计算结果，最后输出结果。
这种方法通过预处理质数和前缀和数组，可以高效地处理每个查询。
