0%

约瑟夫环问题

约瑟夫环

1
2
3
4
5
6
7
8
int main() {
int n, m, i, s = 0;
scanf("%d%d", &n, &m);
for(i = 2; i <= n; i++) {
s = (s + m) % i;
}
printf("%d\n", s + 1);
}

证明

定义 $a_n$ 为从 $0$ 开始,步长为 $1$ ,长度为 $n$ 的递增序列:

$a_n = \{0,1,\dots,n-1\}$

  1. 设 $F(n,m)$ 为 $a_n$ 组成的环上从 $ 0 $ 开始删除第 $ m $ 个数,这个数的位置是 $(m - 1)\ \%\ n$ 。

  2. 删除的数字设为 $ k $ ,从 $k$ 断开组成新序列:$ k+1, k+2 ,\dots,n-1,0,1,\dots,k-2,k-1$

  3. 现在试图找出一个映射函数,该函数可以将一个组成的新序列映射成位置序列($a_{n-1}$)。

    注意到生成的位置序列可以继续使用 $F(n-1,m)$ ,每次使用 $F$ 后都映射一次继续使用,最后剩下的元素映射必定为 $0$ 。

映射前 映射后
$k+1$ $0$
$k+2$ $1$
$n-1$ $n-1-(k+1) = n-k-2$
$0$ $n-k-1$
$1$ $n-k$
$k-2$ $n-3$
$k-1$ $n-2$

设该函数为 $h(x)$ ,忽略参数 $k,n$

利用此映射,可以将一个重新组成的环映射成位置序列。

因此,逆映射可以将一个位置序列还原成刚断开的环

设逆映射为 $g(x) = h^{-1}(x)$

代入 $ k = (m - 1)\ \%\ n$

证明过程略

4.由此,我们可以看出:

  • 当剩下一个数字时,保留的数字的位置是0,此时构成的环为 $a_1$ ;
  • 当剩下两个数字时,此时构成的环为 $g(a_1)$,上一轮位置是0的元素此时的位置是$g(0)$;
  • 当剩下三个数字时,此时构成的环为 $g(g(a_1))$,上一轮位置是0的元素此时的位置是$g(g(0))$;

因此,我们可以代入 $g$,补上参数 $n$,可以得出以下结果:

设最后一个数字 $ x $ ,所在位置是 $ s $ ,

  • 最后一轮中,有 $1$ 个元素,$ x $ 所在位置是 $ 0 $;
  • 在上一轮中,有 $2$ 个元素,$ x $ 所在位置是$(0+m)\ \%\ 2$ ;
  • 在上一轮中,有 $3$ 个元素,$ x $ 所在位置是$((0+m)\ \%\ 2 + m)\ \%\ 3$ ;
  • 在第一轮中,有 $ n $ 个元素,$ x $ 所在位置是$(\dots(((0+m)\ \%\ 2 + m)\ \%\ 3 + m)\dots +m)\ \%\ n$;

返回加1的原因是人类一般习惯从1开始数。

-----------看到底线啦 感谢您的阅读-------------