石油大训练 Little Sub and Johann （博弈SG打表找规律）
Little Sub and Johann
题目描述
Little Sub and Johann are good friends and they often play games together. Recently, they like playing with stones.
They have n piles of stones initially and they should make one of following movements by turns:
1.Erase a pile of stones.
2.Suppose there is a stone pile which has x stones, you can erase y stones from it but the greatest common divisor of x and y should be 1.
If someone cannot make any legal movement, the other person win the game. We all know that Little Sub and Johann are very genius and will always follow the optimal strategy. If Little Sub take the first move, please tell us who will win the game eventually.
They have n piles of stones initially and they should make one of following movements by turns:
1.Erase a pile of stones.
2.Suppose there is a stone pile which has x stones, you can erase y stones from it but the greatest common divisor of x and y should be 1.
If someone cannot make any legal movement, the other person win the game. We all know that Little Sub and Johann are very genius and will always follow the optimal strategy. If Little Sub take the first move, please tell us who will win the game eventually.
输入
There are multiple cases. the first line contains an integer T(1≤T≤100), indicating the number of cases.
There will be two line for each case. The fi rst line contains a integer n(1≤n≤100), indicating the number of stones piles.
The second line will be n integers Ai(1≤Ai≤106), indicating the number of stones in the ith pile.
There will be two line for each case. The fi rst line contains a integer n(1≤n≤100), indicating the number of stones piles.
The second line will be n integers Ai(1≤Ai≤106), indicating the number of stones in the ith pile.
输出
For each case please output exactly one line.
If Little Sub will win, please output ’Subconscious is our king!’. If Johann will win, please output ’Long live with King Johann!’
If Little Sub will win, please output ’Subconscious is our king!’. If Johann will win, please output ’Long live with King Johann!’
样例输入
2
4
1 10 5 7
4
9 2 3 6
样例输出
Subconscious is our king! Long live with King Johann!
题意：给你多堆石子，每次可以将其中一堆取完或者从该堆里面取走和该堆个数互质个数，问最后谁赢。
题解：
一眼看出是裸的博弈SG，打了100的表，但是死活找不出规律，真是菜啊。%%%侯学长
以下是学长思路：
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]} = 4;
sg[6] = mex{sg[0],sg[1],sg[5]} = 2;(缺少sg[2],sg[3],sg[4])
写到这里就可以发现当x为质数，sg[x] = k+1,k表示x是第k个质数。不然sg[x] = sg[y],y为x的最小质因子。
其实找规律不能硬找，需要先理解。
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 #include<cstring>
5 using namespace std;
6 const int maxn=1e6+10;
7 int prime[maxn];
8 int sg[maxn];
9 int fac[maxn];
10 void get_prime()
11 {
12 for(int i=2;i<=maxn;i++)
13 if(prime[i]==0)
14 {
15 for(int j=i+i;j<=maxn;j+=i)
16 {
17 prime[j]=1;
18 if(!fac[j])
19 fac[j]=i;
20 }
21 }
22 }
23
24 /*int gcd(int a,int b)
25 {
26 if(b==0)
27 return a;
28 return gcd(b,a%b);
29 }
30 void dfs(int t)
31 {
32 int vis[1100];
33 if(sg[t]!=-1)
34 return sg[t];
35 memset(vis,0,sizeof(vis));
36 for(int i=1;i<=t;i++)
37 {
38 if(gcd(i,t)==1||t==i)
39 {
40 vis[dfs(t-i)]=1;
41 }
42 }
43 for(int i=0;i<1100;i++)
44 {
45 if(vis[i]==0)
46 return sg[t]=i;
47 }
48 }*/
49 int main()
50 {
51 memset(sg,-1,sizeof(sg));
52 // dfs(100);
53 get_prime();
54 sg[0]=0;
55 sg[1]=1;
56 int k=2;
57 for(int i=2;i<maxn;i++)
58 {
59 if(prime[i]==0)
60 sg[i]=k++;
61 else
62 {
63 if(i%2==0)
64 sg[i]=2;
65 else
66 sg[i]=sg[fac[i]];
67 }
68 }
69 int casen;
70 cin>>casen;
71 int n;
72 while(casen--)
73 {
74 int ans=0;
75 scanf("%d",&n);
76 for(int i=0;i<n;i++)
77 {
78 int x;
79 scanf("%d",&x);
80 ans^=sg[x];
81 }
82 if(ans!=0)
83 {
84 puts("Subconscious is our king!");
85 }
86 else
87 {
88 puts("Long live with King Johann!");
89 }
90 }
91
92
93 }