SHU 418 丢史蒂芬妮

史蒂芬妮,空,白都是no game no life 里的人物，正值这个月15号剧场版即将上映，看得出来，出题人也是同道中人

这是一道勉强算得上博弈的博弈题。因为很那个……有点无法描述

题意：
给你一个 n × m 的棋盘，每次都只能向右，向下，向右下走质数个位置，哪个人先没路走哪个就算输。

思路：
为什么只能是勉强算得上是博弈，整个局势从最开始就是确定的，先手的空只能走一步，要么必赢，要么必输。嘛～ 这倒是很像空白风格的游戏。
我对每个格子从左上向右下判断，如果我能在之前的格子找到任意一个必输的局势，那么我当前位置必赢。由此不断往下递推即可。

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 505;
int Np[MAXN];
bool win[MAXN][MAXN];
vector<int> pr;

bool check(int x, int y)
{
    int l = max(x - 1, y - 1);
    bool res = false;
    for (int i = 0; !res && pr[i] <= l; i++) {
        if (x > pr[i])
            res |= (!win[x - pr[i]][y]);
        if (y > pr[i])
            res |= (!win[x][y - pr[i]]);
        if (x > pr[i] && y > pr[i])
            res |= (!win[x - pr[i]][y - pr[i]]);
    }
    return res;
}

void init()
{
    for (int i = 2; i < MAXN; i++) {
        if (!Np[i])
            pr.push_back(i);
        for (int j = 0; j < (int)pr.size(); j++) {
            int t = pr[j] * i;
            if (t >= MAXN)
                break;
            Np[t] = true;
            if (i % pr[j] == 0)
                break;
        }
    }
    for (int i = 1; i <= 500; i++)
        for (int j = 1; j <= 500; j++)
            win[i][j] = check(i, j);
}

int main()
{
    init();
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        printf("%s\n", win[n][m] ? "Sora" : "Shiro");
    }
    return 0;
}