知识点 - 约瑟夫环（公式总结）

知识点 - 约瑟夫环（公式总结）

一、 $n$个人，1至m报数，问最后剩下来的人的编号

公式

$f(n,m) = (f(n-1,m)+m)\%n$

$f(0,m) = 0$

复杂度 $O(n)$

代码

typedef long long ll;
ll calc(int n, ll m) {
	ll p = 0;
	for (int i = 2; i <= n; i++) {
		p = (p + m) % i;
	}
	return p + 1;//
}

二、 $n$个人， $1$至 $m$报数，问第 $k$个出局的人的编号 ( $k < 10^6$)

公式

$f(n,k) = (f(n-1,k-1)+m-1)\%n + 1$

$f(n-k+1,1) = m\%(n-k+1)$ $if (f == 0) f = n - k + 1$

复杂度 $O(k)$

代码

typedef long long ll;
ll calc(int n, ll m) {
	ll p = 0;
	for (int i = 2; i <= n; i++) {
		p = (p + m) % i;
	}
	return p + 1;//
}

三、 $n$个人， $1$至 $m$报数，问第 $k$个出局的人的编号（ $m < 10^6$）

公式：同上，这里的核心是一下子跳多次，不是一个一个转移

复杂度： $O(m*log(m))$

代码

ll cal2(ll n, ll m, ll k) {
	if (m == 1) return k;
	else {
		ll a = n - k + 1, b = 1;
		ll c = m % a, x = 0;
		if (c == 0) c = a;
		while (b + x <= k) {
			a += x, b += x, c += m * x;
			c %= a;
			if (c == 0) c = a;
			x = (a - c) / (m - 1) + 1;
		}
		c += (k - b) * m;
		c %= n;
		if (c == 0) c = n;
		return c;
	}
}

转载：https://blog.csdn.net/qq_41848675/article/details/101639498