题目地址: LA 4727 Jump
转自博客：shiqi_614
约瑟夫环的问题。
题目给你n,k。n即约瑟夫环的长度，k是淘汰掉从当前开始数的第k个人，然后问你被淘汰的最后三个人是谁。
逆向思维。如果某个人A是最后被淘汰掉的，当最后只剩下一个
人（即A）时，A一定是在0位置（我们从0位置开始，方便取余运算）。那么当只剩下两个人时，A的位置又是在哪呢？引用下约瑟夫环的百度百科：
我们知道第一个人(编号一定是(m-1)%n) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
k k+1 k+2 … n-2,n-1, 0, 1, 2, … k-2
并且从k开始报0。
现在我们把他们的编号做一下转换：
k –> 0
k+1 –> 1
k+2 –> 2
…
…
k-3 –> n-3
k-2 –> n-2
序列1： 1, 2, 3, 4, …, n-2, n-1, n
序列2： 1, 2, 3, 4, … k-1, k+1, …, n-2, n-1, n
序列3： k+1, k+2, k+3, …, n-2, n-1, n, 1, 2, 3,…,k-2, k-1
序列4：1, 2, 3, 4, …, 5, 6, 7, 8, …, n-2, n-1
变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：
∵ k=m%n;
∴ x’ = x+k = x+ m%n ; 而 x+ m%n 可能大于n
∴x’= (x+ m%n)%n = (x+m)%n
得到 x‘=(x+m)%n
我们可以这样理解上面的公式，因为我们进行重新编号的时候，位置编号已经不是原来的位置编号，而是有了一个位移K，使所有的数的位置编号都移动了向左移动了K，如果我们要得到原来的位置编号，那么我们就要把这个当前的编号加上K才行，而K=m%n;，那么我们的问题就解决了。我们可以由一个人的当前位置编号得到它的上一次的位置编号，也就是说当我们知道A是最终的胜利者，并且A最后只有1个人的时候在位置0上，我们可以得出在只有两个人的时候，A在哪个位置上即(0+k)%2，如果递推下去，我们就可以得到n个人时，最后一个人的位置编号。
同理，我们要求倒数第二个被淘汰的人B的位置编号，我们只要在只有两个人时，得到不是的在A的位置位置，那么就是倒数第二个人被淘汰的位置编号（如果这时候A是0，那么B就是1，反之就是0），然后递推回去，我们就可以得到n个人时，B的位置编号。三个人同理。
最后把编号+1变成1到n的即可。
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(int)(b);--i)
int main(int argc, char const *argv[])
{int T,n,k; scanf("%d",&T);while(T--&&scanf("%d%d",&n,&k)==2){int x=(k+2)%3;REP(i,4,n) x=(x+k)%i;printf("%d ", x+1);x=(k+1)%2;REP(i,3,n) x=(x+k)%i;printf("%d ", x+1);x=0;REP(i,2,n) x=(x+k)%i;printf("%d\n", x+1);}return 0;
}