首页 > 代码库 > shuoj 418 丢史蒂芬妮(素数筛+sg函数)
shuoj 418 丢史蒂芬妮(素数筛+sg函数)
丢史蒂芬妮
代码:
#include<bits/stdc++.h> using namespace std; const int N=500+5; int SG[N][N]; bool S[N]; vector<int>prime; bool not_prime[N]; void get_SG(int n) { memset(SG,0,sizeof(SG)); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { memset(S,false,sizeof(S)); for(int k=0;k<prime.size();k++) { if(j-prime[k]>=1)S[SG[i][j-prime[k]]]=true; else break; } for(int k=0;k<prime.size();k++) { if(i-prime[k]>=1)S[SG[i-prime[k]][j]]=true; else break; } for(int k=0;k<prime.size();k++) { if(j-prime[k]>=1&&i-prime[k]>=1)S[SG[i-prime[k]][j-prime[k]]]=true; else break; } for(int k=0;k<N;k++) if(!S[k]) { SG[i][j]=k; break; } } } } void get_prime(int n) { memset(not_prime,false,sizeof(not_prime)); for(int i=2;i<=n;i++) { if(!not_prime[i]) { prime.push_back(i); for(int j=i+i;j<=n;j+=i) { not_prime[j]=true; } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); get_prime(500); get_SG(500); int t; cin>>t; while(t--) { int n,m; cin>>n>>m; if(SG[n][m])cout<<"Sora"<<endl; else cout<<"Shiro"<<endl; } return 0; }
shuoj 418 丢史蒂芬妮(素数筛+sg函数)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。