题目大意：

有一堆石子总共有\(n\)个，两个玩家轮流去取，每次至少取一个石子。先手玩家在第一次取石子的时候至多取\(n-1\)个，之后每个玩家每次最多只能取他对手上一次取石子的\(k\)倍。 比如某个玩家在某次取走\(q\)个石子，轮到他的对手取石子了，对手最多只能取\(k * q\)个石子。当某个玩家不能取到石子时就输了，对手获胜。

输入

第一行是一个整数t，表示接下来有t组测试（ \(t <= 20\) ）
接下来每行是2个整数\(n\)和\(k\)，（\(2 <= n <= 10^8, 1 <= k <= 10^5\)）

输出

对于每组测试用例，输出以"Case N: "作为开头，N是测试用例的编号。接下来如果先手玩家有必胜策略，输出他第一次能取的最少的石子的个数，如果它没有必胜策略，输出"lose"。

样例输入

1
2
3
4
5
6
5
16 1
11 1
32 2
34 2
19 3

样例输出

1
2
3
4
5
Case 1: lose
Case 2: 1
Case 3: 3
Case 4: lose
Case 5: 4

题目分析

这个问题的性质非常复杂，需要先从特殊情况分析，然后归纳总结。

首先可以通过打表找规律： 用 \(a[i][j]\) 表示总共有 \(i\) 个石子，当前玩家最多取 \(j\) 个石子，是否有必胜策略。

  1. 显然当 \(i <= j\) 时，当前玩家可以一次取完所有石子，必胜。
  2. 当 \(i > j\) 时，从 1 到 \(j\) 枚举当前玩家可以取的石子个数， 只要有一个能导致对手必败， \(a[i][j]\) 必胜，否则 \(a[i][j]\) 必败。 \[ a[i][j] = \begin{cases} 1, & \text{if i <= j} \\[2ex] \bigvee\limits_{1<=s<=j}!a[i-s][k*s], & \text{if i > j} \end{cases} \] 这个算法的时间复杂度为 \(O(n^3)\) ，时间复杂度过高，显然无法通过测试，只能用来分析简单的Case。

Python 代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#!/usr/bin/env python
#-*- coding:utf-8 -*-

import sys

n = int(sys.argv[1])
k = int(sys.argv[2])

arr = [[0 for i in range(n*k+1)] for i in range(n*k+1)]
for i in range(1, n*k + 1):
    for j in range(i, n*k + 1):
        arr[i][j] = 1

for i in range(2, n+1):
    for j in range(1, i):
        for s in range(1, j+1):
            if arr[i-s][k*s] = 0:  # 取走 s 个石子，导致对手必败
                arr[i][j] = 1
                break

for i in range(1, n+1):
    if arr[i][i-1] == 0:
        print(i)
#### 1. 分析 \(k = 1\) 情况 当\(k = 1\)时，打表的结果是[1, 2, 4, 8, 16, 32, 64, 128 ...]，即当 \(n=2^k\) 时先手必败，否则先手必胜。

如果 \(n\) 不是 2 的幂，必胜策略是：先手玩家取石子的个数为 \(n\) 用二进制表示时最末尾的 1 ， 由于个数限制，后手玩家不能取走倒数第二个 1 ，因此不能降低 \(n\) 中 1 的个数。设他取走的石子个数是 \(q\)， \(q\) 用二进制表示末尾仍然有一个 1，这和剩余石子的个数用二进制表示时末尾的 1 在同一位置。 先手玩家又可以取走这个末尾的 1，此策略保证先手玩家总有石子可取，先手必胜。

2. 分析 \(k = 2\) 情况

当 \(k = 2\)时，打表的结果是[1, 2, 3, 5, 8, 13, 21, 34, 55, 87, 142 ...]， 发现了斐波那契数列，这个问题也叫做 Fibonacci NIM 。结论是当 \(n\) 是斐波那契数时，先手必败，否则先手必胜。 解决这个问题需要用到 Zeckendorf 定理：任何一个正整数都可以写成不相邻斐波那契数的和，这可以用数学归纳法证明。

用 \(F[n]\) 表示第 \(n\) 个斐波那契数，有如下性质： \[ F[n] = F[n-1] + F[n-2] \tag{1} \] \[ 2*F[n-2] > F[n-1] \tag{2} \] \[ 2*F[n-3] < F[n-1] \tag{3} \] 结合这 3 条性质，可以证明当 \(n\) 是斐波那契数时必败，否则必胜。具体证明过程见 \(k >= 3\) 的情况。

3. 分析 \(k >= 3\) 情况

这是是 Schwenk's Nim 的一种特殊情况。Schwenk's Nim 要求：如果某个玩家在某次取的石子个数是 \(q\) ， 那么轮到对手玩家时，对手这次最多只能取 \(f(q)\) 个石子，但并没有限定 \(f(q)\) 的具体形式。 在本题目中，相当于限制 \(f(q) = k*q\) 。

构造序列\(B_f = (b_0, b_1, b_2, b_3, ...)\)，满足如下递推式： \[ b_i = \begin{cases} 1, & \text{if i = 0} \\[2ex] b_{i-1} + b_j, & \text{if i >= 1} \end{cases} \] 在上式中 \(b_j\) 是集合 \(\{b_0, b_1, b_2, ..., b_{i-2}, b_{i-1}\}\) 中满足 \(f(b_j) >= b_{i-1}\) 的最小的数。

Holshouser 在 Dynamic One-Pile NIM 中指出： 用二元组 \((N, x)\) 表示当前总共有 \(N\) 个石子，最多只能取 \(x\) 个石子，是否有必胜策略。把 \(N\) 表示成 \(B_f\) 中成员的和： \(N=\sum\limits_{j=1}^{j=m}b_{ij}\), 满足 \(b_{i1} < b_{i2} < ... < b_{im}\)， 并且对任意的\(s\)，\(1 <= s <= m\), 满足 \(\sum\limits_{j=1}^{j=s-1}b_{ij} <= b_{is}\) ，满足这个关系也叫稳定拆分。 那么当 \(x >= b_{i1}\) 时先手必胜，先手的必胜策略是拿走 \(b_{i1}\) 个石子；当 \(x < b_{i1}\) 时，先手必败。

可以结合一个具体的例子来看，当 \(k = 3\)时，必败状态的序列为： [1, 2, 3, 4, 6, 8, 11, 15, 21, 29, 40, 55, 76, 105, 145, 200]，递推式如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
2 = 1 + 1
3 = 2 + 1
4 = 3 + 1
6 = 4 + 2
8 = 6 + 2
11 = 8 + 3
15 = 11 + 4
21 = 15 + 6
29 = 21 + 8
40 = 29 + 11
55 = 40 + 15
76 = 55 + 21
...
分析这个必败序列，以 \(N = 76\) 为例， \(76 = 55 + 21\)，因为 \(3 * 21 >= 55\)，如果先手取的石子数大于等于 \(21\) ，后手可以一次取完剩余所有石子必胜；如果先手取的石子数小于 \(21\) ，那么剩余的石子个数一定大于 \(55\) 个，比如 \(55 + p\) 个。接下来又要对 \(p\) 进行分析，这是一个递归问题。可以用数学归纳法证明（或者用反证法证明）。

我们需要证明的结论是：对于序列 \(B_f\) 中的某个整数 \(b_i\) ，由 \(B_f\) 的定义我们知道 \(b_i = b_{i-1} + b_j\)，其中（ \(k * b_j >= b_{i-1}\) ），对于任意小于 \({b_i}\) 的正整数 \(x\)，将 \(b_i - x\) 用 \(B_f\) 中的数字做稳定拆分，即 \(b_i - x = b_{i1} + b_{i2} + ... + b_{ij}，(b_{i1} < b_{i2} < ... < b_{ij})\) ，有结论： \(k * x >= b_{i1}\)

用强数学归纳证明上述结论：

  1. 当 \(n = 0\) 时，没有符合条件的\(x\)，结论成立。

  2. 假设当任意\(i < n\)的时，结论都成立，现在证明结论 \(b_n\) 也成立。 由定义知道 \(b_n\) 可以写成形式： \(b_n = b_{n-1} + b_{i}\)， 其中 \(k * b_{i} >= b_{n-1}\)，\(b_n - x = b_{n1} + b_{n2} + ... + b_{nj}\)。
    分 2 种情况讨论：
    如果 \(x >= b_{i}\) ，那么 \(k * x\) >= \(k * b_{i} >= b_{n-1}\)，结论成立。
    如果 \(x < b_{i}\)，\(b_n - x = b_{n-1} + (b_{i} - x)\)，对于 \(b_{i} - x = b_{i1} + b_{i2} + ... + b_{ij}\)，通过归纳假设知: \(k * x >= b_{i1}\) 由于对 \(b_n - x\)的拆分是稳定的， \(b_n - x\)拆分后所有的和小于 \(b_{n-1}\)，所以 \(b_n - x = b_{i1} + b_{i2} + ... + b_{ij} + b_{n-1}\)，并且 \(k * x >= b_{i1}\)。结论成立。

综合上述 1 和 2 可知：对于任意 \(n \in N\)，结论都成立。

对于这个题目，如果初始石子个数 \(n\) 不在必败序列 \(B_f\) 中，先手只要每次都取拆分后最小的分量，就可以永远保证有石子可取，先手必胜。如果 \(n\) 不在 \(B_f\)中，先手不能一次取完所有石子，只能到达必胜状态，先手必败。

代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>

int b[2000000] = {1};

void solve(int n, int k) {
    int i = 0;
    int j = 0;
    while (b[i] < n) {
        i++;
        while (k * b[j] < b[i-1]) {
            j++;
        }
        // 找到最小的j，满足 k * b[j] >= b[i-1]
        b[i] = b[i-1] + b[j];
    }
    if (b[i] == n) {
        printf("lose\n");
        return;
    }

    i--;
    while (n > b[i]) {
        n -= b[i];
        j = i;
        while (k * b[i] >= b[j] || n < b[i]) {
            i--;
        }
    }
    printf("%d\n", b[i]);
}

int main() {
    int c, n, k;
    int t;
    scanf("%d", &t);

    for (c = 1; c <= t; c++) {
        scanf("%d%d", &n, &k);
        printf("Case %d: ", c);
        solve(n, k);
    }
}

题目网址：http://poj.org/problem?id=3922

参考文章：Dynamic One-Pile NIM