ACM模版

描述

题解

先吐个槽，题面有毒，这题的出题人或者翻译人语文水平堪忧啊……这里说的分成几等分只取其中一份有问题，应该是只留下其中的一份，剩下的全部拿走。真是无语=_=

这个题，没有多想，直接打表，打表后发现胜败和是否为素数有一定的关系，于是又加了一个素数筛，然后打表（代码 One）的结果如下：

此时，打表的范围在 1e3 内，于是又尝试打表 1e4 以内，发现结果依然没有什么变化，于是大胆猜测，是否只有这几个值特别？其他都是符合规律的？哦，忘了说规律了，素数差不多都是 0 ，而合数差不多都是 1 ，打表的具体结果告诉我们，素数中除了 2、17 都是 0 ，而合数除了 1、16、34、289 都是 1 ，当然，这个既不是素数又不是偶数的 0 结果也是 0 ，那么直接几个判断就能解决（代码 Two）啊~~~

对了， 1 是 TAK ， 0 是 NIM 。

代码

One：

#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

const int MAXN = 10000;

bool flag[MAXN];

/* * 素数筛选，判断小于MAXN的数是不是素数 * notprime是一张表，false表示是素数，true表示不是 */
bool notprime[MAXN];

void init()
{
    memset(notprime, false, sizeof(notprime));
    notprime[0] = notprime[1] = true;
    for (int i = 2; i < MAXN; i++)
    {
        if (!notprime[i])
        {
            if (i > MAXN / i)   // 阻止后边i * i溢出（或者i,j用long long)
            {
                continue;
            }
            // 直接从i * i开始就可以，小于i倍的已经筛选过了
            for (int j = i * i; j < MAXN; j += i)
            {
                notprime[j] = true;
            }
        }
    }

    memset(flag, 0, sizeof(flag));

    for (int i = 2; i < MAXN; i++)
    {
        flag[i] |= (!flag[i - 1]);
        if (flag[i])
        {
            continue;
        }

        int tmp = sqrt(i) + 1;
        for (int j = 2; j <= tmp; j++)
        {
            if (i % j == 0)
            {
                flag[i] |= (!flag[j]);
                flag[i] |= (!flag[i / j]);
                if (flag[i])
                {
                    break;
                }
            }
        }
    }
}

int main()
{
    init();

    for (int i = 0; i < MAXN; i++)
    {
        if (notprime[i] && flag[i] == 0)
        {
            printf("%d-%d\n", i, flag[i]);
        }
        else if (!notprime[i] && flag[i] == 1)
        {
            printf("%d-%d\n", i, flag[i]);
        }
    }

    return 0;
}

Two：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

int n;

bool is_prime(int x)
{
    if (x < 2)
    {
        return false;
    }

    int tmp = sqrt(x) + 1;
    for (int i = 2; i < tmp; i++)
    {
        if (x % i == 0)
        {
            return false;
        }
    }

    return true;
}


int main()
{
    int T;
    scanf("%d", &T);

    while (T--)
    {
        scanf("%d", &n);
        bool flag = false;
        if (is_prime(n))
        {
            if (n == 2 || n == 17)
            {
                flag = !flag;
            }
        }
        else
        {
            if (n > 2 && n != 16 && n != 34 && n != 289)
            {
                flag = !flag;
            }
        }

        puts(flag ? "TAK" : "NIE");
    }

    return 0;
}