QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#62346 | #1863. Yes, Prime Minister | lmeowdn | ML | 0ms | 0kb | C++17 | 1.2kb | 2022-11-18 12:17:03 | 2022-11-18 12:17:03 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define eb emplace_back
#define fi first
#define se second
#define pc __builtin_popcount
typedef pair<int,int> pii;
typedef vector<int> vi;
long long read() {
long long res=0, w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {res=res*10+c-'0'; c=getchar();}
return res*w;
}
const int N=4e7+9;
int pr[N],tot,vst[N],nxt[3][N];
int T,x[N];
void pre(int n=4e7) {
vst[1]=1;
rep(i,2,n) {
if(!vst[i]) pr[++tot]=i;
for(int j=1;j<=tot&&pr[j]*i<=n;j++) {
vst[i*pr[j]]=1;
if(i%pr[j]==0) break;
}
}
per(i,n/2,0) {
if(!vst[i]) nxt[1][i]=i;
else nxt[1][i]=nxt[1][i+1];
if(!vst[2*i-1]) nxt[2][i]=i;
else nxt[2][i]=nxt[2][i+1];
}
}
signed main() {
T=read();
pre();
rep(i,1,T) {
int x=read();
if(x==0) {
puts("3");
} else if(x>0&&!vst[x]) {
puts("1");
} else if(x>0&&(!vst[2*x+1]||!vst[2*x-1])) {
puts("2");
} else {
if(x<0) x=-x;
printf("%lld\n",2*x+1+min(2*(nxt[1][x+1]-x-1)+1,2*(nxt[2][x+2]-x-2)+2));
}
}
return 0;
}
详细
Test #1:
score: 0
Memory Limit Exceeded
input:
10 -2 -1 0 1 2 3 4 5 6 7