51nod1074 约瑟夫环V2 [思维题]

$约瑟夫环V2$

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

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

$(2 le N le 10^{18}, 2 le M le 1000)$

---

$color{red}{正解部分}$

考虑先将第一个人$(M-1)\%N$处决, 然后去掉$(M-1)\%N$得到下表格第二行,
从 $M\%N$ 开始重新编号, 得到下表格第三行, 设 $F[i]$ 长度为 $i$ 的环最后出去的人的编号 .

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

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

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

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

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

---

$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
", cur+1);
}

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