http://hi.baidu.com/huicpc0207/item/f11a06f36ecfe91484d278fddisscus里说有比O(n)还低的DP方法，之前我也构造出来了，不过是不正确的。比O(n)低的DP方法？？？
问了问院长老师，希望她能给个比较好的算法哦哦哦
归纳、构造数列：根据k=1,k=2找到思路，找出必败态即可。
总结：
1、多研究思考些有难度的数学问题，自己找到办法。
2、复杂问题总是有简单办法的。
3、难题代码实现一般很容易！
#include<stdio.h>
#include<string.h>
#include<math.h>
int a[1000005],r[1000005];
int solve(int n,int k)
{
int i,j,ans;
a[0]=0;r[0]=0;
for (i=1,j=0;i<=1000000;i++)
{
a[i]=r[i-1]+1;
while (j+1<i && a[j+1]*k <a[i])
j++;
r[i]=a[i]+r[j];
if (r[i]>=n)
break;
}
if (a[i]==n)
return 0;
while (i>=1)
{
if (n==a[i])
return a[i];
else
if (n>a[i])
n-=a[i];
i--;
}
return ans;
}
int main()
{
int t,cas=0,n,k,ans;
scanf("%d",&t);
while (t--)
{
scanf("%d%d",&n,&k);
ans=solve(n,k);
printf("Case %d: ",++cas);
if (!ans)
printf("lose\n");
else
printf("%d\n",ans);
}
return 0;
}