题目分析

题目本质

这是一个经典的约瑟夫环（Josephus Problem）问题。每隔 $M$ 个人出列，最后剩下的那个人就是胜利者。我们需要找出最后幸存的人的编号。

算法思路

题目内容

有 $N$ 个小孩围成一圈玩报数游戏，从第一个人开始报数，数到 $M$ 的人出列，再由下一个人重新从 $1$ 开始报数，数到 $M$ 的人再出圈，依次类推，最后留下的小孩为胜利者。对于给定的 $N，M$ ，你能找出谁是最后的王者吗?

输入描述

一行两个数字，$N$ 和 $M$ ，$(3<=N<=10^6)(1<=M<=10^6)$

输出描述

最后获胜小孩的编号

样例1

输入

8 3

输出

7

说明

$8$ 个人围成一圈,每报数 $3$ 就退出的循环如下：

1 2 3 4 5 6 7 8

第 $1$ 次报数之后，$3$ 退出，剩下：

1 2 4 5 6 7 8 (现在从 $4$ 开始报数)

第 $2$ 次报数之后，$6$ 退出，剩下：

1 2 4 5 7 8 (现在从 $7$ 开始报数)

第 $3$ 次报数之后，$1$ 退出，剩下：

2 4 5 7 8 (现在从 $2$ 开始报数)

第 $4$ 次报数之后，$5$ 退出，剩下：

2 4 7 8 (现在从 $7$ 开始报数)

第 $5$ 次报数之后，$2$ 退出，剩下：

4 7 8 (现在从 $4$ 开始报数)

第 $6$ 次报数之后，$8$ 退出，剩下：

4 7 (现在从 $4$ 开始报数)

最后一次报数之后，$4$ 退出，剩下：

7

所以，最后留下来的人编号是 $7$ 。