算法

(打表) $O(n^(3/2))$

弄懂最优策略，小蓝想赢是要砍到剩余长度恰好能让小蓝赢的长度，具有变换最优子结构的性质
这里我的代码在官网可以AC，Acwing的机子还是太慢了

python 代码

N = 100010
st = [False]*N
f = [False]*N#False认为小乔赢，True认为小蓝赢
def init():
    st[2] = False
    for i in range(3,N):
        j = 2
        while j * j <= i:
            if i % j == 0:
                st[i] = True
            j += 1

if __name__ == '__main__':
    init()
    q = []
    for i in range(2,N):
        if st[i] == False:
            q.append(i)
    t = int(input())
    for i in range(2,N):
        for j in range(len(q)):
            if q[j] <= i:
                if f[i - q[j]] == False:
                    f[i] = True
            else:
                #由于是顺序遍历，如果比i大不需要考虑了
                break
    for i in range(t):
        n = int(input())
        if f[n] == True:
            print(1)
        else:
            print(0)