只要用質數的篩子觀念處理即可。
複雜度是 nlg(lgn)
重點在於欲處理後的判斷"至否為質數"的三個條件
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include<stdio.h> #include<stdlib.h> #include<string.h> #include<assert.h> #include<vector> #define N 1000000 bool seive[N+1]; int nptr[N+1]; int RES[N+1]; std::vector<int>prime; int main() { memset(seive,true,sizeof(seive)); seive[1]=false; for(int lx=2;lx<=N;lx++) { if(seive[lx]) { prime.push_back(lx); for(int ly=2;ly*lx<=N;ly++) seive[lx*ly]=false; } } for(int ly=1;ly<=N;ly++) nptr[ly]=ly; for(int lx=0;lx<prime.size();lx++) { int tmp; if((N/prime[lx])<=1) break; for(int ly=(N/prime[lx]);ly>=2;ly--) { tmp=nptr[prime[lx]*ly]; nptr[prime[lx]*ly]=nptr[prime[lx]*(ly-1)]; nptr[prime[lx]*(ly-1)]=tmp; } } for(int lx=1;lx<=N;lx++) RES[nptr[lx]]=lx; free(nptr); //for(int lx=1;lx<=N;lx++) // assert((RES[lx]>0)&&((RES[lx]>=lx)||seive[RES[lx]])); int nn,M; int T,lT;scanf("%d",&T); for(lT=1;lT<=T;lT++) { scanf("%d %d",&nn,&M); if((RES[M]>nn)||seive[RES[M]]||(RES[M]<M)) printf("Geng Jian malheureux roi mauvaise!!\n"); else printf("%d\n",RES[M]); } return 0; } |
沒有留言:
張貼留言