lance.h

lance

0%

ccpc网络赛05

发表于 更新于 分类于

1005(博弈论)

…比赛的时候死活没找到规律

SG 函数结论

显然$SG(1)=0,SG(prime)=1$

对于非 1,prime 的数,其后继个数即为所有大于 1 的因子个数(不可以拆成 1 个自己).

以 27 为例子:$$SG(27)=mex \{SG^{27}(1), SG^3(9), SG^9(3)\}$$

有一个显然的结论,如果拆分成$even*k$,则$SG^{even}(k)=0$,此时因为必然有$SG^n(1)=0$,所以这种拆分没有什么意义,立马得出,只有 2 为因子的$2^k$的 SG 值全为 1….然后…然后就没什么可以推的了….打表找规律

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//我的打表代码
#include<bits/stdc++.h>
using namespace std;
bool not_prime[100];
vector<int> prime;
void init(){
  memset(not_prime,false,sizeof not_prime);
  not_prime[0]=not_prime[1]=true;
  for(int i=2;i<100;i++){
    if(!not_prime[i]){
      not_prime[i]=false;
      prime.push_back(i);
      if(i>100/i)break;
      for(int j=i*i;j<100;j+=i){
        not_prime[j]=true;
      }
    }
  }
}
int mex(vector<int> &sgs_p){
  for(int i=0;i<=100;++i){
    int tag=0;
    for(auto j:sgs_p){
      if(i==j){
        tag=1;break;
      }
    }
    if(tag==0)return i;
  }
}
inline int xorPower(int np,int b){int ans=0;while(np--){ans^=b;}return ans;}
int sg(int n){
  if(n==1)return 0;
  else if(!not_prime[n])return 1;
  vector<int> sgs;
  for(int i=1;i<n;++i){
    if(n%i==0){
      sgs.push_back(xorPower(n/i,sg(i)));
    }
  }
  return mex(sgs);
}
void solve(){
  init();
  for(int i=1;i<=30;++i)
    cout<<i<<" : "<<sg(i)<<endl;
  return ;
}
int main()
{
  solve();
  return 0;
}

样例中有一组考究的 3,9,27,分别是 3 的 123 次方,我们知道,他们的 SG 值也是 123,因为比 2 大的质数都是奇数,分解的时候不会出现偶数次 xor 导致为 0 的情况,而当数中有但不全是 2 的因子时…

我们看 $4*3=12$

有$$SG(12)=mex \{SG^{12}(1), SG^2(6), SG^3(4), SG^4(3), SG^6(2) \}$$

显然的,唯一一组不是 0 的就是把所有 2 的次幂放在一起,即分解为$k*2^m$的时候,此时又有$SG(2^k)=1$故 2 的次幂只能被计一次,12 是只有一个质因数的,当有多个质因子时,如 36,我们将看到决定 SG 值的是$SG^3(12)$,故每多一个质因子就多计 1.

结论

每个数的 SG 值为:

  • 若为 1,为 0
  • 若为 2 的次幂,或者 prime 为 1
  • 若为偶数,为非 2 质因子个数+1
  • 若为奇数,为质因子个数

实现

  • 数据范围为 1e9,我们直接筛一个 5e4 的素数表
  • 求每个数的 SG 值
  • 最后求 Nim 和,非 0 先手必胜
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//筛法直接用埃氏筛就行了
//**1,longlong如果巨量操作,显著慢于int
//**2,筛法是很慢的,多筛一点就差很多了
//即,算好要求,不要多筛不要乱开longlong
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 45000;
//const int MAXN=1e5;
bool notprime[MAXN]; // 值为 false 表示素数，值为 true 表示非素数
int prime[MAXN];
int p=0;
void init() {
    memset(notprime, false, sizeof(notprime));
    notprime[0] = notprime[1] = true;
    for (ll i = 2; i < MAXN; i++)
        if (!notprime[i]) {
            prime[p++]=i;
            for (ll j = i * i; j < MAXN; j += i)//
                notprime[j] = true;
        }
}

int frac(int n) {
    int sum = 0, flag = 0;
    for (int i=0;i<p;++i) {
        if (n < prime[i]) break;
        while (n % prime[i] == 0) {
            if (prime[i] != 2) sum++;
            else flag = 1;
            n /= prime[i];
        }
    }
    if (n > 1) sum++;
    return sum + flag;
}

void solve() {
    init();
    int t;
    cin >> t;
    for (int i = 0; ts < t; ++i) {
        int n;
        cin >> n;
        int res = 0;
        for (int j = 0; j< n; ++j) {
            int tmp;
            cin >> tmp;
            res ^= frac(tmp);
        }
        cout << (res ? "W" : "L") << endl;
    }
}

int main() {
    solve();
    return 0;
}