这个题目是这样的，一堆石子有n个，首先第一个人开始可以去1-(n-1)个，接下来两人轮流取石子，每个人可取的石子数必须是一个不超过上一次被取的石子的K倍的整数。
现在求对于一堆数量为n的石子是否为必胜态，如果是的话，先手者第一次最少可以取多少石子？
这个题目是一个典型的K倍动态减法游戏。构造两个数列，然后直接判断就好了。
至于数列的构造原理，我自己弄得也不是很透彻，等我透彻了再写写吧。
对于输出最小的可行解，就是逐步减小并且判断就好了。
1 #include <iostream> 2 #include <cstdio> 3 #define maxn 5000000 4 using namespace std; 5 6 int a[maxn],b[maxn],k,n,i,j,ans; 7 8 int main() 9 { 10 int t,cas=0; 11 scanf("%d",&t); 12 while (t--) 13 { 14 scanf("%d%d",&n,&k); 15 a[0]=b[0]=1; 16 i=j=0; 17 for (; a[i]<n; i++)//构造序列 18 { 19 a[i+1]=b[i]+1; 20 while (a[j+1]*k<a[i+1]) j++; 21 if (a[j]*k<a[i+1]) b[i+1]=b[j]+a[i+1]; 22 else b[i+1]=a[i+1]; 23 } 24 printf("Case %d: ",++cas); 25 if (n==a[i]) printf("lose "); 26 else 27 { 28 for (; n; i--) 29 if (n>=a[i]) n-=a[i],ans=a[i]; 30 printf("%d ",ans); 31 } 32 } 33 return 0; 34 }