d312 - 抓兔子

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算在給定區間 [a, b] 內，有多少個數字是兔子窩，也就是說，這些數字無法透過任何兔子窟的兔子跳躍到達。兔子從 k >= 2 的兔子窟開始，每次跳 k 格。兔子窩出現在無法被任何兔子跳躍到達的座標上。

解題思路

首先，兔子無法跳到的點就是質數。因此，問題可以轉化為計算區間 [a, b] 內質數的個數。 程式碼使用埃拉托斯特尼篩法 (Sieve of Eratosthenes) 找出 1 到 10000000 之間的質數。 然後，使用前綴和 (Prefix Sum) 技巧，計算出每個位置為止的質數個數。 最後，對於每個查詢 (a, b)，計算 p[b] - p[a-1]，得到區間 [a, b] 內的質數個數，即不需要放置陷阱的座標點的個數。

複雜度分析

• 時間複雜度: O(N log log N + Q)，其中 N 是 10000000，Q 是查詢次數。埃拉托斯特尼篩法的時間複雜度是 O(N log log N)，計算前綴和的時間複雜度是 O(N)，每個查詢的時間複雜度是 O(1)。
• 空間複雜度: O(N)，用於儲存質數標記和前綴和。

程式碼

#include <iostream>
using namespace std;
int p[10000001]={1,1},ans,t,x,y;
int main(){
	for(int i=2;i<=3163;++i)
		for(int j=i+i;j<=10000000;j+=i)
			p[j]=1;
	for(int i=0;i<=10000000;++i){
		if(p[i]==0)
			++ans;
		p[i]=ans;
	}
	cin >> t;
	while(t--){
		cin >> x >> y;
		if(y<x)swap(x,y);
		cout << p[y]-p[x-1] << "\n";
	}
}