牛客網 Wannafly挑戰賽15 C題《出隊》

連結：https://www.nowcoder.com/acm/contest/112/C

來源：牛客網

題目描述

約瑟夫問題(https://baike.baidu.com/item/約瑟夫問題)，n個人，1 2報數 1出隊( 就是體育課的時候1 2報數  1出隊，2留下)，q次詢問，每次求第x個人是第幾個出隊的

輸入描述:

第一行兩個數n,q
接下來q行，每行一個數x，表示詢問      

輸出描述:

一行輸出一個詢問的答案      

示例1

輸入

4 3
2
3
4      

輸出

3
2
4      

說明

1 2 3 4圍成一圈，第一輪：1 2報數，1出隊，2留下，3出隊，4留下，第二輪，2出隊，4留下      

備注:

q≤500000
n和x≤1e18      

ps：是個環！

補個自己的想法，看了代碼，好像是，看x的位置是奇數還是偶數來進行下一步的操作，進行下一步就代碼，ans有加上上輪的還剩的數量/2.

牛客網：Toocold的代碼：

#include<bits/stdc++.h>
using namespace std;
 
#define lc o<<1
#define rc o<<1|1
#define fi first
#define se second
#define pb push_back
#define CLR(A, X) memset(A, X, sizeof(A))
#define bitcount(X) __builtin_popcountll(X)
typedef double DB;
typedef long long LL;
typedef pair<int, int> PII;
 
const int INF = 0x3f3f3f3f;
const int N = 1e5+10;
 
LL solve(LL n, LL x) {
//    if(n == 1) return 1;
//    printf("? = %lld %lld\n", n, x);
    if(x%2 == 0) return x/2+1;
    else {
        if(n%2 == 0) {
            return n/2+solve(n/2, x/2);
        }
        else {
            LL t = n/2;
            return t+1+solve(t, (x/2-1+t)%t);
        }
    }
}
 
int main() {
    LL n; int q;
    scanf("%lld%d", &n, &q);
    while(q--) {
        LL x; scanf("%lld", &x); x--;
        printf("%lld\n", solve(n, x));
    }
    return 0;
}