砍 柴

解题思路:

注意事项:

参考代码:import math
def get_primes(max_val):
   v = [True] * (max_val + 1)
   for x in range(2, max_val + 1):
       if not v[x]:
           continue
       for y in range(x * 2, max_val + 1, x):
           v[y] = False
   primes = [x for x in range(2, max_val + 1) if v[x]]
   return primes
def win(x):
   if memo[x] != 0:
       return memo[x] == 1
   if x <= 1:
       return False
   for i in range(bis(x), -1, -1):
       if not win(x - primes[i]):
           memo[x] = 1
           return True
   memo[x] = -1
   return False
def bis(x):
   l = 0
   r = len(primes)
   while l < r:
       m = (l + r) // 2
       if primes[m] <= x:
           l = m + 1
       else:
           r = m
   return l-1
T = int(input())
woods = [int(input()) for _ in range(T)]
max_wood = max(woods)
primes = get_primes(max_wood)
memo = [0] * (max_wood + 1)
for wood in woods:
   result = 1 if win(wood) else 0
   print(result)