了解这个难题的解决方案

Question

我在编码竞赛中做了一个谜题,我坚持一个问题.基本上我不明白有人能够达到这个解决方案.这个谜题是

Alice和Bob玩下面的游戏.他们选择N号来玩.规则如下:

1. 鲍勃首先出场,两名球员交替出场.
2. 在他/她的回合中,玩家可以从N中减去任何小于N的素数(包括1).由此获得的数字是新的N.
3. 在他/她的回合中无法行动的人将失去游戏.

假设两者都发挥得最好,谁赢了比赛？

给定的解决方案是

int main() {
  long int T, N;
  for(scanf("%ld", &T); T > 0; T--) {
    scanf("%ld", &N);
    if (N % 4 == 1) {
      printf("ALICE wins\n");
    } else {
      printf("BOB wins\n");
    }
}

Answer 1

这是一种Nim游戏.最终面临N = 1失败的球员.如果N % 4 != 1,鲍勃可以拿1,2或3来做下一个N ? 1 (mod 4),让爱丽丝处于失败的位置.否则,如果N ? 1 (mod 4)在开始时,Alice可以反击Bob的动作? 1 (mod 4)再次为Bob 留下一个号码.