题目
题目描述
有一种有趣的游戏，玩法如下：
玩家：2人；
道具：N颗石子；
规则：
游戏双方轮流取石子；每人每次取走若干颗石子（最少取1颗，最多取K颗）；石子取光，则游戏结束；最后取石子的一方为胜。假如参与游戏的玩家都非常聪明，问最后谁会获胜？
输入描述
输入仅一行，两个整数N和K。
输出描述
输出仅一行，一个整数，若先手获胜输出1，后手获胜输出2。
示例1
输入
23 3
输出
1
备注
对于全部数据，\(1 \leq N \leq 10^5,1 \leq K \leq N\) 。
题解
知识点：博弈论。
经典的Bash游戏，考虑设 \(f_i\) 表示有 \(i\) 个石子时先手是否必胜。
我们尝试打表，假设 \(k = 3\) ：
i 0 1 2 3 4 5 6 7 8 9
f 0 1 1 1 0 1 1 1 0 1
注意到 \(k+1 \mid n\) 时，先手必败，否则必胜。
证明数归容易得到。
时间复杂度 \(O(1)\)
空间复杂度 \(O(1)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, k;
cin >> n >> k;
cout << (n % (k + 1) ? 1 : 2) << '\n';
return 0;
}