本文出自：

题目地址：

题目意思：

给你编号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;}