King's Game

为了铭记历史，国王准备在阅兵的间隙玩约瑟夫游戏。它召来了 n(1\le n\le 5000)n(1≤n≤5000) 个士兵，逆时针围成一个圈，依次标号 1, 2, 3 ... n1,2,3...n。

第一轮第一个人从 11 开始报数，报到 11 就停止且报到 11 的这个人出局。

第二轮从上一轮出局的人的下一个人开始从 11 报数，报到 22 就停止且报到 22 的这个人出局。

第三轮从上一轮出局的人的下一个人开始从 11 报数，报到 33 就停止且报到 33 的这个人出局。

第 n - 1n−1 轮从上一轮出局的人的下一个人开始从 11 报数，报到 n - 1n−1 就停止且报到 n - 1n−1 的这个人出局。

最后剩余的人是幸存者，请问这个人的标号是多少？

第一行一个整数表示测试组数：T(0 < T\le5000)T(0<T≤5000) 。

每组数据占一行，包含一个整数 nn，表示 nn 个人围成一圈。

共 TT 行。对每组数据，输出幸存者的编号。

2

2

3

2

2

对于第一组数据，一开始报到 11 的人即标号为 11 的人退出，幸存者是 22 号。

对于第二组数据，一开始报到 11 的人即标号 11 的人退出。接着 22 号报 11，33 号报 22，报到 22 的人即 33 号退出。幸存者是 22 号。

/*

hdu 5643 BestCoder Round #75

这个类似于约瑟夫环，只是第i次报i的人被干掉

简单粗暴点就是打表，另外一种就是递推

我们要求的是n个人时最后存活的是谁f[n]

但是我们发现杀掉一个人之后从它的下一位开始重新编号

就成了求f[n-1]的解，所以考虑递推

      i+1                i               i-1

0 1 2 3 4 5 6 7  -> 1 2 3 4 5 6 7 -> 1 3 4 5 6 7

                    0 1 2 3 4 5 6    5 0 1 2 3 4

对于第i次而言，我们要干掉第n-i+1个人,而且会从下一位重新编号

所以i->i+1时  每个数的编号相对增加了n-i+1  然后进行取模即可

*/

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <stack>

#include <map>

using namespace std;

typedef long long ll;

typedef long double ld;

#define lson (i<<1)

#define rson ((i<<1)|1)

const int maxn = 5005;

int dp[maxn];

int main()

{

    int T,m,n;

    scanf("%d",&T);

    while(T--)

    {

        dp[1] = 0;

        scanf("%d",&n);

        for(int i = 2; i <= n; i++)

        {

            dp[i] = (dp[i-1]+n-i+1)%i;

        }

        dp[n] += 1;

        printf("%d\n",dp[n]);

    }

    return 0;

}