约 瑟 夫 环 V 2 约瑟夫环V2 约瑟夫环V2

N个人坐成一个圆环（编号为1 - N），从第1个人开始报数，数到K的人出列，后面的人重新从1开始报数。问最后剩下的人的编号。

例如：N = 3，K = 2。2号先出列，然后是1号，最后剩下的是3号。

( 2 ≤ N ≤ 1 0 18 , 2 ≤ K ≤ 1000 ) (2 \le N \le 10^{18}, 2 \le K \le 1000) (2≤N≤1018,2≤K≤1000)

<mstyle mathcolor="red"> 正 解 部 分 </mstyle> \color{red}{正解部分} 正解部分

考虑先将第一个人 ( M − 1 ) % N (M-1)\%N (M−1)%N处决, 然后去掉 ( M − 1 ) % N (M-1)\%N (M−1)%N得到下表格第二行,
从 M % N M\%N M%N 开始重新编号, 得到下表格第三行,

0 0 0 1 1 1 … ( M − 1 ) % N (M-1)\%N (M−1)%N … N − 1 N-1 N−1
M % N M\%N M%N ( M + 1 ) % N (M+1)\%N (M+1)%N … ( M + M − 1 ) % N (M+M-1)\%N (M+M−1)%N … ( M + N − 2 ) % N (M+N-2)\%N (M+N−2)%N
0 0 0 1 1 1 … ( M − 1 ) % ( N − 1 ) (M-1)\%(N-1) (M−1)%(N−1) … N − 2 N-2 N−2

推出递推式: F [ i ] = ( F [ i − 1 ] + M ) % i F[i] = (F[i-1] + M) \% i F[i]=(F[i−1]+M)%i .

直接计算 时间复杂度为 O ( N ) O(N) O(N), 不能通过此题, 考虑加速转移过程,

注意到转移只受到 模数 的影响, 可以在 模数 这里 “动手脚”,
设当前状态为 i i i, 则可以直接转移到 F [ i + k ] F[i+k] F[i+k], 其中 k = ⌊ i − F [ i ] M ⌋ k = \lfloor \frac{i - F[i]}{M} \rfloor k=⌊Mi−F[i]​⌋ .

这里是从 0 0 0 到 N − 1 N-1 N−1 标号, 因此输出答案时要加 1 1 1 .

<mstyle mathcolor="red"> 实 现 部 分 </mstyle> \color{red}{实现部分} 实现部分

#include<bits/stdc++.h>
#define reg register
typedef long long ll;

const int maxn = 1e6 + 5;

int M;

ll N;

void Work(){
        scanf("%lld%d", &N, &M);
        ll cur = 0;
        for(reg ll i = 2; i <= N; i ++){
                if(cur + M >= i) cur += M, cur %= i;
                else{
                        ll k = std::min(N-i+1, (i-cur)/M);
                        cur += k*M, i += k - 1;
                }
        }
        printf("%lld\n", cur+1);
}

int main(){
        int T; scanf("%d", &T);
        while(T --) Work();
        return 0;
}