【gym 101955K】Let the Flames Begin（约瑟夫环问题）

题目链接
大意是$n$个人围成一圈（ID依次为$1\sim n$），每$k$个人踢掉1个，求第$m$个被踢掉的人的ID。

1. $O(k\log n)$解法（未AC）

参考知乎回答
按该回答中的方式进行编号，第$m$个被踢掉的人编号为$mk$。
$n=10,k=3$的情况如图所示：

可知编号$mk+d$的人下一次编号为$n+m(k-1)+d(1\le d<k)$。
令$N=n+m(k-1)+d$，则$m=[\frac{N-n-1}{k-1}]$，$N^{\prime }=mk+d=N-n+[\frac{N-n-1}{k-1}]$。
用上述式子不断迭代，最后求出的就是该玩家的id。

记$kn+1-N=D$，则$D^{\prime }=\lceil \frac{Dk}{k-1}\rceil$。
复杂度为$O(k\log n)$。

可以写出如下代码：

#include<bits/stdc++.h> 
#define ll long long
using namespace std;
ll f(ll n, ll m, ll k){ // n-people, m-th, k-cycle
	__int128 D = (__int128)k * (n - m) + 1;
	while((__int128)k * n + 1 - D > n){
		D = (D * k + k - 2) / (k - 1);
	}
	return (__int128)k * n + 1 - D;
}
int main(){
    int T, cas = 0;
    scanf("%d", &T);
    ll n, m, k;
	while(T--){
		scanf("%lld%lld%lld", &n, &m, &k);
		printf("Case #%d: %lld\n", ++cas, f(n, m, k));
	}
	return 0;
}

但是无法通过这题。

2. $O(\min (m,k\log n))$解法

记$f(n,m,k)$为问题的答案（0和$n$等价），则有递推式$f(n,m,k)=k+f(n-1,m-1,k)\mathrm{m}\mathrm{o}\mathrm{d}n$。
复杂度$O(m)$。

若$n>k$，那么上述方法中多次取模是没有必要的，可以改为批量处理：
$$\begin{gathered} f(n,m,k)=kx+f(n-x,m-x,k)\mathrm{m}\mathrm{o}\mathrm{d}n \\ (kx+f(n-x,m-x,k)\le n+k-1) \end{gathered}$$
复杂度$O(\min (m,k\log n))$。

AC代码如下：（要写成非递归形式，否则栈空间不够）

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i=l; i<=r; ++i)
#define per(i, r, l) for(int i=r; i>=l; --i)
#define ll long long
using namespace std;

ll f(ll n, ll m, ll k){
    if(k == 1) return m;
    ll ret = 0, x = 1, t = m;
    while(t){
    	t -= x;
    	ret = (k * x + ret) % (n - t);
    	if(!ret) ret = n - t;
    	x = min(t, (n - t - ret) / (k - 1) + 1);
	}
    return ret;
}

int main() {
    int T, cas=0;
    scanf("%d",&T);
    while(T--) {
        ll n, m, k;
        scanf("%lld%lld%lld", &n, &m, &k);
        printf("Case #%d: %lld\n", ++cas, f(n, m, k));
    }
    return 0;
}