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;
}