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

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

公式

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

f ( 0 , m ) = 0 f(0,m) = 0 f(0,m)=0

复杂度 O ( n ) O(n) 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 n n个人， 1 1 1至 m m m报数，问第 k k k个出局的人的编号 ( k < 1 0 6 k < 10^6 k<106)

公式

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

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

复杂度 O ( k ) O(k) 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 n n个人， 1 1 1至 m m m报数，问第 k k k个出局的人的编号（ m < 1 0 6 m < 10^6 m<106）

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

复杂度： O ( m ∗ l o g ( m ) ) O(m*log(m)) 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;
	}
}