题解
2025-11-09 22:24:58
发布于:广东
36阅读
0回复
0点赞
史诗级猎奇做法。
观察样例,发现和答案和素性强相关。
首先打了一个素数筛,没筛 因为 显然是合法的。
然后交上去 WA 了 3 个点。
再次观察样例,发现 没被写进去。
所以我们推测 很重要。
前往 OEIS,输入 ,发现了这条结果。

然后这题就被我水过了。
#include <iostream>
#include <cstdio>
using namespace std;
bool vis[1000005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
for(int i = 2; i <= 1000; i++){
if(vis[i]) continue;
for(int j = i * 2; j <= 1000000; j += i){
vis[j] = 1;
}
}
vis[1] = vis[4] = 0;
int t;
cin >> t;
while(t--){
int n;
cin >> n;
cout << (vis[n] ? "NO\n" : "YES\n");
}
return 0;
}
全部评论 1
666这题我观察样例没观察出来,打表得到的规律
1周前 来自 江西
0











有帮助,赞一个