e539 - 00967 - Circular
題目描述
題目要求計算給定區間 [i, j] 內循環質數的數量。循環質數是指，將其數字循環移位後，每次移位後的數字仍然是質數。
解題思路
程式首先使用埃拉托斯特尼篩法預先計算出 1 到 1000000 之間的質數。然後，定義一個函數 isrecprime 來判斷一個數字是否為循環質數。該函數通過將數字的數字循環移位 8 次，並檢查每次移位後的數字是否為質數來實現。最後，使用動態規劃預處理出前綴循環質數的數量，以便快速計算給定區間內的循環質數數量。具體來說，dp[i] 儲存小於等於 i 的循環質數的數量。對於每個輸入區間 [x, y]，程式計算 dp[y] - dp[x-1]，得到該區間內的循環質數數量，並根據數量輸出相應的訊息。
複雜度分析
- 時間複雜度: O(NloglogN + M * 8 + Q)，其中 N 是 1000000，M 是 1000000，Q 是查詢次數。O(NloglogN) 是埃拉托斯特尼篩法的時間複雜度，O(M * 8) 是判斷每個數字是否為循環質數的時間複雜度，O(Q) 是處理查詢的時間複雜度。
- 空間複雜度: O(N)，主要用於儲存質數表和動態規劃陣列。
程式碼
#include <iostream>
using namespace std;
int dp[1000005],x,y;
bool p[1000005]={1,1};
bool isrecprime(int v){
int t=v,k=1;
while(t){
t/=10;
k*=10;
}
for(int i=0;i<8;++i){
if(p[v])return 0;
v+=k*(v%10);
v/=10;
}
return 1;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
for(int i=2;i<=1000;++i){
for(int j=i+i;j<=1000000;j+=i){
p[j]=1;
}
}
for(int i=2;i<=1000000;++i){
if(isrecprime(i)){
dp[i]=dp[i-1]+1;
}
else{
dp[i]=dp[i-1];
}
}
while(cin >> x){
if(x==-1)break;
cin >> y;
int ans=dp[y]-dp[x-1];
if(!ans){
cout << "No Circular Primes.\n";
}
else if(ans==1){
cout << ans << " Circular Prime.\n";
}
else{
cout << ans << " Circular Primes.\n";
}
}
}