圣桥桐香

takanashi_mifuru · 2024-09-15 17:19:34 · 题解

首先容易发现，对 n 取模了之后相同的点只能有一个后手必胜，因为假设有两个，那个大的就可以通过直接导成小的来达成先手必胜。

然后给 SG 函数打个表，你发现如果 m>120n，最后就一定会获胜，你就把这个范围内的 SG 函数处理出来就行了。

然后爆了，因为每次都要花根号回去找，但是你发现把同余数的判掉之后我只需要让这个先手必败点往后找点给他们标记成必胜就可以把他打成 n\sqrt n，然后就过了。

#include<bits/stdc++.h>
using namespace std;
int q,n;
bool SG[60000005];
bool done[500005];
int main(){
    scanf("%d%d",&q,&n);

    int lim=n;
    SG[0]=false;
    done[0]=true;
    for(int j=1;j*j<=lim;j++){
        SG[j*j]=true;
    }
    int pos=0;
    for(int i=1;i<=120*lim;i++){
        pos++;
        if(pos==lim)pos=0;
        if(done[pos]){
            SG[i]=true;
            continue;
        }
        if(!SG[i]){
            done[pos]=true;
            for(int j=1;j*j<=lim;j++){
                SG[i+j*j]=true;
            }
            continue;
        }
    }
    while(q--){
        int tmp;
        scanf("%d",&tmp);
        if(tmp>120*lim){
            putchar('F');
        }
        else{
            if(SG[tmp])putchar('F');
            else putchar('B');
        }
    }
    return 0;
}