题目链接：https://ac.nowcoder.com/acm/contest/940/C/
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

kotori和一些偶像们围成一圈，一共有n个偶像（包括kotori自己），她们的序号顺时针从1到n。现在她们从1号开始进行顺时针报数：1,2,1,2,1……
每个报到2的人出列。直到剩下最后一个人为止。那么这个剩下的人就能被选中发专辑出道啦！
kotori可以暗箱操作决定自己的序号。她很想发专辑，于是向聪明的你求助，初始序号设定为多少才可以呢？

输入描述

第一行输入一个正整数t，代表共有t组样例。
第2行到第t+1行，每行一个正整数n，代表一次询问。
(1≤t≤10000，1≤n≤10^18)

输出描述

一共t行，每行一个正整数，代表kotori的初始序号。

输入

1
5

输出

3

说明

依次出列的序号是2,4,1,5，故3号胜出，可以发专辑。

解题思路

题意:约瑟夫环问题。
思路:数据过大不能用递归解决，打表找规律得2*(n-cnt)+1, 其中cnt为不大于n的最大2的整数幂。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int t;
    ll n;
    scanf("%d", &t);
    while (t--) {
        ll cnt = 1;
        scanf("%lld", &n);
        while (cnt << 1 <= n)
            cnt <<= 1;
        printf("%lld\n", ((n - cnt) << 1) + 1);
    }
    return 0;
}