2014
02-10

# a simple stone game

After he has learned how to play Nim game,Mike begins to try another stone game which seems much easier.

The game goes like this:Two players start the game with a pile of n stones.They take stones from the pile in turn and every time they take at least one stone.The one who goes first can take at most n-1 stones for his first move .from then on a player can take at most k times as many stones as his opponent has taken last time.For example,if one player take m stones in his turn,then the other player can taken at most k * m stones next time.The player who takes the last stone wins the game.suppose that those two players always take the best moves and never make mistakes,your job is to find out who will definitely win the game.

The first line contains a integer t,indicating that there are t test cases following. (t<=20).Each test is a line consisting of two integer n and k.(2<=n<=10^8,1<=k<=10^5).

The first line contains a integer t,indicating that there are t test cases following. (t<=20).Each test is a line consisting of two integer n and k.(2<=n<=10^8,1<=k<=10^5).

6
16 1
11 1
32 2
34 2
19 3
100000000 100000

Case 1: lose
Case 2: 1
Case 3: 3
Case 4：lose
Case 5: 4
Case 6: 912

HintHint
When k=1,the first player will definitely lose if the initial amount of stones is
in the set {2,4,8,16,32,….}. Let’s call this kind of set “first-player-lose set”
(必败点集合)

When k=2,the first-player-lose set is {2,3,5,8,13,21,34,57…},which happens to be
the Fibonacci sequence starting from 2.

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<math.h>
#include<set>
#include<vector>
#define MAXN 15
#define INF 1000
using namespace std;
int no[2000000],maxok[2000000];//no储存的是lose的数。  maxok【i】存的是在i之前能组成的最大的数；
int main()
{
int i,j,n,m,k,t,c,ca=0;
for(scanf("%d",&t);t--;)
{
ca++;
scanf("%d%d",&n,&k);
if(n<=k+1)//n<=k+1时一定是输；
{
printf("Case %d: lose\n",ca);
continue;
}
int x=0,y=0;
no[0]=maxok[0]=1;
while(no[x]<n)
{
x++;
no[x]=maxok[x-1]+1;//在x之前，最大的能符合的数是maxok【x-1】、加1后就不符合。
while(no[y+1]*k<no[x])//找小于no[x]的最大数:例子k=3时有15得到4
y++;
if(no[y]*k<no[x])//前面得到的数可能不符合条件
maxok[x]=no[x]+maxok[y];//如果符合直接得no[x]+maxok[y]；例子中推得15+maxok[3]
else
maxok[x]=no[x];//否则能组成最大的数为本身。
}
if(no[x]==n)//刚好组成n  说明这个数属于no数组。即不能由符合条件的数组成，lose！
{
printf("Case %d: lose\n",ca);
continue;
}
int ans;
while(n)
{
if(n>=no[x])//不断的减去最大的数，剩下的最小的数就是了。
{
ans=no[x];
n-=no[x];
}
x--;
}
printf("Case %d: %d\n",ca,ans);
}
return 0;
}
/*
k=3时：
no={1,2,3,4,6,8,11,15,21,29
maxok=1,2,3,5,7,10,14,20
*/

1. （这个有点扯。首先，还没听说什么病一过性生活就会死。再者….）看完我都想抽死你。你要相信地府办案效率。呵呵呵呵呵呵。

2. （这个有点扯。首先，还没听说什么病一过性生活就会死。再者….）看完我都想抽死你。你要相信地府办案效率。呵呵呵呵呵呵。

3. 为什么for循环找到的i一定是素数叻，而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak，而你每次取余都用的是原来的m，也就是n

4. 可以参考算法导论中的时间戳。就是结束访问时间，最后结束的顶点肯定是入度为0的顶点，因为DFS要回溯