本文出自：http://blog.csdn.net/dr5459

题目地址：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4198

题目意思：

给你编号1~n的数，每次从格k个删一个数，会有一个顺序

让你给出最后三个被删除的数

解题思路：

这题很明显就是约瑟夫的变形

假设编号从0~n-1

我们令f[1]=0   表示还剩1个时最后被删掉的一定是0

那么经典的约瑟夫公式变为f[n]=（f[n-1]+k）%n

表示剩n个时最后一个被删掉的

我们可以想到，如果我们知道剩2个的时候，被删除的是谁，剩3个的时候被删掉的是多少

然后再根据上面的公式就可以搞定了

通过本题，让我更进一步的理解了约瑟夫公式

下面是两种不同代码：

直接推出倒数被删掉的（未证明）

#include
#include
#include
using namespace std;

int main()
{
int n,k;
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
int x;
x=(k+2)%3;
for(int i=4;i<=n;i++)
x=(x+k)%i;
printf("%d ",x+1);
x=(k+1)%2;
for(int i=3;i<=n;i++)
x=(x+k)%i;
printf("%d ",x+1);
x=0;
for(int i=2;i<=n;i++)
x=(x+k)%i;
printf("%d\n",x+1);
}
return 0;
}

下面给出自己推的

#include
#include
#include
using namespace std;

int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,k;
scanf("%d%d",&n,&k);
int ans1=0;
int ans2,ans3;
for(int i=2;i<=n;i++)
{
ans1 = (ans1+k)%i;
if(i==2)//当剩下2个的，倒数第二个被删除的就是和倒数第一个不同的，答案只有0,1
{
ans2 = !ans1;
}
else if(i==3)//当剩下3个的时候，就是在0,1,2里面找不是ans1,ans2的
{
ans2 = (ans2+k)%i;
int v[3];
memset(v,false,sizeof(v));
v[ans1] = 1;
v[ans2] = 1;
for(int j=0;j<3;j++)
if(!v[j])
{
ans3 = j;
break;
}
}
else
{
ans2 = (ans2+k)%i;
ans3 = (ans3+k)%i;
}
}
ans1 = ans1+1;
ans2 = ans2+1;
ans3 = ans3+1;
printf("%d %d %d\n",ans3,ans2,ans1);

}  
return 0;  

}