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

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

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

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

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

记 $k n + 1 - N = D$ ，则 $D'=\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$ 等价），则有递推式 $\mod n$ 。
复杂度 $O (m)$ 。

若 $n > k$ ，那么上述方法中多次取模是没有必要的，可以改为批量处理：
$\mod n\\(kx+f(n-x,m-x,k)\le n+k-1)$
复杂度 $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;
}

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

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

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

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

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