f479 - 質數成長
題目描述
題目描述了一種植物的成長模式，其每天的成長速度由連續質數列表決定。給定第 N 天和節數 K，要求輸出植物第 K 節對應的字母（A, B, 或 C）。如果 K 超出第 N 天的節數，則輸出 #。字母的分配方式是按照質數列表的餘數來決定：餘數為 1 時輸出 A，餘數為 2 時輸出 B，餘數為 0 時輸出 C。
解題思路
首先，需要預先計算出前 N 個質數的和，這可以使用埃拉托斯特尼篩法生成質數，然後使用前綴和來快速計算。接著，判斷 K 是否超出第 N 天的節數。如果 K 超出，則輸出 #。否則，計算 K 對應的字母。具體來說，找到前綴和中大於等於 K 的第一個質數和，然後計算 K 與前一個質數和的差的餘數，根據餘數輸出 A、B 或 C。
複雜度分析
- 時間複雜度: O(N + Q)，其中 N 是質數列表的最大長度（在本例中為 110000），Q 是查詢次數（<= 10000）。埃拉托斯特尼篩法的時間複雜度為 O(N log log N)，前綴和計算為 O(N)，每次查詢的時間複雜度為 O(log N) (二分查找)，但由於題目 N 的範圍不大，可以優化為線性查找，因此整體查詢時間複雜度為 O(Q)。
- 空間複雜度: O(N)，用於存儲質數列表和前綴和。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
int pt[110001],it;
int adp[110001],n,k;
char p[110001]={1};
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
int main(){
for(int i=2;i<=332;++i)
for(int j=i+i;j<=110000;j+=i)
p[j]=1;
for(int i=0;i<=110000;++i)
if(p[i]==0){
pt[it]=i;
if(it>0)
adp[it]=pt[it]+adp[it-1];
else
adp[it]=pt[it];
++it;
}
while(n=read()){
k=read();
if(adp[n-1]<k)
putchar_unlocked('#');
else{
int it2=0;
while(adp[it2]<k)
++it2;
int total=(k-adp[it2-1])%3;
if(total==1)
putchar_unlocked('A');
else if(total==2)
putchar_unlocked('B');
else
putchar_unlocked('C');
}
putchar_unlocked('\n');
}
}