问题的解可以分解为多个子问题的解，而这些子问题之间存在重叠
问题的最优解可以通过子问题的最优解推导出来
所以采用了dp算法.
首先找到最长的木头,通过它来打dp表,这样就可以涵盖问题中的所有木头长度
然后遍历长度范围内的素数
再对dp做分析,dp(x)所表示的是输赢的状态,如果砍去木头后,状态变为输,则说明当前会赢.当然,dp[0]和dp[1]都为输
因为只对赢的状态进行了赋值,所以默认的初始化都为0.

python代码

def is_prime(x):
    if x < 2:
        return False
    for i in range(2,int(x**(1/2))+1):
        if x % i == 0:
            return False
    return True

t = int(input())
arr = []
primes = []
res = []
for _ in range(t):
    arr.append(int(input()))#初始化输入
n = max(arr)
primes = [x for x in range(2,n + 1) if is_prime(x)]
dp = [0] * (n + 1)
#dp(x),x means current length,the function refers to the player's situation.
dp[0] = dp[1] = 0
for i in range(2,n+1):
    for p in primes:
        if p > i:
            break
        if dp[i-p] == 0:
            dp[i] = 1
            break
for k in arr:
    print(1 if dp[k] == 1 else 0)