【翻译】A simple stone game

时间:2024-01-02 21:02:38

题目描述

在学会了如何玩尼姆游戏之后,迈克开始尝试另一种看起来很多的石头游戏。 简单点。 游戏是这样的:两个玩家用一堆n块石头开始游戏。他们轮流从堆里取石头,每次至少取一块石头 一堆又一堆,每次他们至少拿走一块石头。先走的人最多能拿到。 N-1石头作为他的第一步。从那时起,一个玩家最多能拿到k倍的石头。 他的对手上次赢了。例如,如果一个玩家在轮到他的时候拿到了m块石头,那么另一个玩家就会拿到另一个。 玩家下次最多可以拿km的石头。拿最后一块石头的人赢了这场比赛。 假设这两个球员总是采取最好的动作,从不犯错误,你的工作就是。 找出谁肯定会赢这场比赛。

输入输出格式

输入格式:

第一行包含一个整数t,表示下面有t个测试用例(t<=20). 每个测试用例都是由两个整数n和k组成的一行。(2 ≤ n ≤ 10810^{8}108 , 1 ≤ k ≤ 10510^{5}105).

输出格式:

对于每个测试用例,输出一行以‘CaseN:’开头的行,N是事例编号。然后,如果第一个玩家可以确保赢球,打印出他在第一回合中应该拿到的最少的石头数。否则,打印“lost”。请注意,冒号后面有一个空格。

暗示:

当k=1时,如果石头的初始数量在{2, 4, 8, 16, 32, . . .}这样一组数列中的话。让我们把这种数列称为"先手输的集合" 当k=2时,先手输的集合是{2, 3, 5, 8, 13, 21, 34, 57, . . .},它恰好是从2开始的Fibonacci数列

输入输出样例

输入样例:

5 16 1 11 1 32 2 34 2 19 3

输出样例:

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