題目描述

區(qū)間質(zhì)數(shù)個(gè)數(shù)

輸入輸出格式

輸入格式：

?

一行兩個(gè)整數(shù) 詢問次數(shù)n，范圍m

接下來n行，每行兩個(gè)整數(shù) l,r 表示區(qū)間

?

輸出格式：

?

對于每次詢問輸出個(gè)數(shù) t，如l或r?[1,m]輸出 Crossing the line

?

輸入輸出樣例

輸入樣例#1： 復(fù)制

2 5 1 3 2 6

輸出樣例#1： 復(fù)制

2 Crossing the line

說明

【數(shù)據(jù)范圍和約定】

對于20%的數(shù)據(jù) 1<=n<=10 1<=m<=10

對于100%的數(shù)據(jù) 1<=n<=1000 1<=m<=1000000 -10^9<=l<=r<=10^9 1<=t<=1000000

第一眼肯定會(huì)想到素?cái)?shù)篩法，但還需將此算法進(jìn)行改進(jìn)。

如果每一次記錄當(dāng)前這個(gè)數(shù)之前有幾個(gè)是素?cái)?shù)，則再求某一區(qū)間內(nèi)的素?cái)?shù)個(gè)數(shù)就變得極為容易。（注意：在求區(qū)間[L,? R]內(nèi)的素?cái)?shù)個(gè)數(shù)時(shí)，不能直接用num[R] - num[L],顯然這樣減少一個(gè)計(jì)算了一個(gè)數(shù)。

例如：計(jì)算區(qū)間[2, 8]內(nèi)的素?cái)?shù)個(gè)數(shù)，

? ? ? ? ?? 數(shù)字：1? 2? 3? 4? 5? 6? 7? 8? 9? 10

? ? ?? 前綴和：0? 1? 2? 2? 3? 3? 4 ? 4? 4? 4?

num[8] - num[2] = 4 - 1 = 3,顯然是錯(cuò)的，所以應(yīng)該減去他的前一個(gè)數(shù)的前綴和，即num[R] - num[L-1]）

?

素?cái)?shù)篩法模板（加計(jì)數(shù)素?cái)?shù)前綴和）

void init(){memset(notprime, false, sizeof(notprime));memset(num, 0, sizeof(num));notprime[0] = notprime[1] = true;num[0] = 0; num[1] = 0;for(int i = 2; i < maxn; i++){if(!notprime[i]){num[i] = num[i-1] + 1;if(i > maxn/i) continue;for(int j = i*i; j < maxn; j += i)notprime[j] = true;}else num[i] = num[i-1];} }

?

?

ac代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<string>using namespace std; typedef long long LL; const int maxn = 1e6+5;bool notprime[maxn]; int num[maxn];int n, m; int l, r;void init(){memset(notprime, false, sizeof(notprime));memset(num, 0, sizeof(num));notprime[0] = notprime[1] = true;num[0] = 0; num[1] = 0;for(int i = 2; i < maxn; i++){if(!notprime[i]){num[i] = num[i-1] + 1;if(i > maxn/i) continue;for(int j = i*i; j < maxn; j += i)notprime[j] = true;}else num[i] = num[i-1];} }int main() {init();scanf("%d%d", &n, &m);while(n--){scanf("%d%d", &l, &r);if(l < 1||r > m) printf("Crossing the line\n");else printf("%d\n", num[r] - num[l-1]);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的P1865 A % B Problem (素数筛法，前缀和)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。