xtu寒假做题1月7日题解

xtu oj 1339

提示：筛法，前缀和

首先看到求 $(a,b)$ 的答案，并且询问的次数很多，预处理的复杂度不高，就可以想到又是前缀和。

那么我们就需要预先处理出所有的答案。

按照题目的要求做就好，首先算出所有的素数，然后按照要求模拟即可。

由于说的是连续的奇素数平均值，可以知道只有2是偶素数，所以不要2即可。

有个无用的条件：连续的奇素数平均值不能是素数，可以知道必然不是素数，反证法即可：由于是平均值，一定处在两者之间，如果平均值是素数，那么一定不是连续的，矛盾即可证。

#include <stdio.h>typedef long long ll;#define N 1001002int np[N], prime[N], op = 0; int sum[N];void init() {// ------------------埃氏筛法-素数---------------------for (int i = 2; i < N; ++i){if (!np[i]) prime[++op] = i;if (!np[i] && i < N / i) {for (int j = i * i; j < N; j += i)np[j] = 1; // 埃筛 }}// --------------------------------------------------for (int i = 2; i < op; ++i){if (np[(prime[i] + prime[i + 1]) / 2]) // 思考这行是否需要sum[(prime[i] + prime[i + 1]) / 2] = 1;}for (int i = 1; i < N; ++i)sum[i] += sum[i - 1];}int main() {init();int T, a, b;scanf("%d", &T);while (T--){scanf("%d%d", &a, &b);printf("%d\n", sum[b] - sum[a - 1]);}return 0; }

总结

以上是生活随笔为你收集整理的xtu寒假做题1月7日题解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。