hznu 校赛 Little Sub and Johann

hznu 校赛 Little Sub and Johann"/>

hznu 校赛 Little Sub and Johann

Little Sub and Johann

这个题打个SG函数表找个规律就可以了，

先跑了前100个sg函数的值，

#include<bits/stdc++.h>
#define exp 1e-8
#define mian main
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
#define pb push_back
#define PI  acos(-1.0)
#define inf 0x3f3f3f3f
#define w(x) while(x--)
#define int_max 2147483647
#define lowbit(x) (x)&(-x)
#define gcd(a,b) __gcd(a,b)
#define pq(x)  priority_queue<x>
#define ull unsigned long long
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define pl(a,n) next_permutation(a,a+n)
#define ios ios::sync_with_stdio(false)
#define met(a,x) memset((a),(x),sizeof((a)))
using namespace std;
const int N=1e6+10;
int f[N],sg[N],s[N],num,;
void get_f(int x)
{num=0;for(int i=1;i<x;i++){if(__gcd(x,i)==1)f[++num]=i;}f[++num]=x;
}
void get_sg(int n)
{sg[0]=0;for(int i=1;i<=n;i++){get_f(i);met(s,0);for(int j=1;j<=num&&f[j]<=i;j++)s[sg[i-f[j]]]=1;for(int j=0;j<=n;j++){if(s[j]==0){sg[i]=j;break;}}}
}
int main()
{get_sg(100);for(int i=0;i<=100;i++)printf("%d : %d\n",i,sg[i]);
}

然后又手写了5,6个才发现了规律

sg[0]=0;

sg[1]=mex{sg[0]}=1;

sg[2]=mex{sg[0],sg[1]}=2;

sg[3]=mex{sg[0],sg[1],sg[2]}=3;

sg[4]=mex{sg[0],sg[1],sg[3]}=2=sg[2];

sg[5]=mex{sg[0],sg[1],sg[2].sg[3],sg[4]}=5;

sg[6]=mex{sg[0],sg[1],sg[5]}=2=sg[2]

当x是质数时，sg值为：如果x是n个素数，那么sg[x]=n+1;也就是素数表中的位置+1

当x是合数时，sg[x]=sg[y],   y为x的最小素因子

所以

#include<bits/stdc++.h>
#define exp 1e-8
#define mian main
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
#define pb push_back
#define PI  acos(-1.0)
#define inf 0x3f3f3f3f
#define w(x) while(x--)
#define int_max 2147483647
#define lowbit(x) (x)&(-x)
#define gcd(a,b) __gcd(a,b)
#define pq(x)  priority_queue<x>
#define ull unsigned long long
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define pl(a,n) next_permutation(a,a+n)
#define ios ios::sync_with_stdio(false)
#define met(a,x) memset((a),(x),sizeof((a)))
using namespace std;
const int N=1e6+10;
int f[N],sg[N],s[N],num,n,prime[N];
void get_f(int x)
{num=0;for(int i=1;i<x;i++){if(__gcd(x,i)==1)f[++num]=i;}f[++num]=x;
}
void get_sg(int n)
{sg[0]=0;for(int i=1;i<=n;i++){get_f(i);met(s,0);for(int j=1;j<=num&&f[j]<=i;j++)s[sg[i-f[j]]]=1;for(int j=0;j<=n;j++){if(s[j]==0){sg[i]=j;break;}}}
}
void getprime(int N)
{memset(prime,0,sizeof(prime));for(int i=2;i<=N;i++){if(!prime[i]){prime[++prime[0]]=i;sg[i]=prime[0]+1;}for(int j=1;j<=prime[0]&&prime[j]<=N/i;j++){prime[prime[j]*i]=1;sg[i*prime[j]]=sg[prime[j]];if(i%prime[j]==0)break;}}
}
int main()
{getprime(1000000);sg[1]=1;get_sg(100);/*for(int i=0;i<=100;i++)printf("%d : %d\n",i,sg[i]);*/int t;sc(t);while(t--){scanf("%d",&n);int ans=0;int x;for(int i=1;i<=n;i++){scanf("%d",&x);ans^=sg[x];}if(ans)printf("Subconscious is our king!\n");elseprintf("Long live with King Johann!\n");}
}