“纽劢科技杯”第十六届同济大学程序设计竞赛暨上海邀请赛同步赛 J-张老师的游戏

传送门

题目描述

    在空闲时间，张老师习惯性地和菜哭武玩起了取石子游戏，这次的游戏规则有些不同，在他们面前有n堆石子，其中，第i堆石子的个数为a[i]，现在制定规则如下：
    从张老师开始，两个人轮流取石子，每次可以从任意一堆中取走x个石子，其中x必须严格小于这堆石子的总数并且能够被这堆石子的个数整除，谁先无法继续取走石子就算失败！
    例如，只有一堆石子，个数为6，张老师首先可以取走的石子个数为1，2或者3个。
    现在给定n堆石子每一堆的石子数，张老师希望你帮他确定在双方最优策略下他能否赢得游戏。

链接：https://acm.nowcoder.com/acm/contest/637/J
来源：牛客网

输入描述:

    第一行一个整数n(1<=n<=100,000)
    第二行n个整数，分别代表每一堆石头的个数，保证所有数据为小于等于10

的正整数

输出描述:

输出一行，Win或者Lose，表示张老师能否获得胜利

示例1

输入

3

2 2 1

输出

Lose

示例2

输入

2

2 9

输出

Win

博弈，后继状态是$n-a_{i}$
$a_{i}$表示除n外的其他因子
打表发现SG函数是该数质因子里有多少个2

#include <bits/stdc++.h>

using namespace std;

const int maxn = ;

int SG[maxn], S[maxn], f[maxn];

void getSG(int n) {

    S[] = ;

    for (int i = ; i <= n; i++) {

        memset(S, , sizeof(S));

        int cnt = ;

        int temp = i;

        f[cnt++] = ;

        for (int j = ; j < temp; j++) {

            if (temp % j == ) {

                f[cnt++] = j;

            }

        }

        sort(f, f + cnt);

        for (int j = ; j < cnt; j++) {

            S[SG[i-f[j]]] = ;

        }

        for (int j = ; ; j++) {

            if (!S[j]) {

                SG[i] = j;

                break;

            }

        }

    }

}

int sg(int x) {

    int ret = ;

    while (x %  == ) ret++, x /= ;

    return ret;

}

int main() {

   // getSG(1000);

   // for (int i = 1; i <= 500; i++) cout << SG[i] << ",";

    int n;

    scanf("%d", &n);

    int flag = ;

    for (int i = ; i < n; i++) {

        int x;

        scanf("%d", &x);

        flag ^= sg(x);

    }

    if (flag) puts("Win");

    else puts("Lose");

    return ;

}