#45. 猴子选大王 1

猴子选大王 1

【题目描述】

有一群进化程度很高的猴子,它们不再通过群殴产生猴王,而是采用一种非常文明的方法选出新的猴王。

猴群里有 n 只猴子,它们在篝火旁围坐成一个圈:其中一只猴子是 1 号,沿顺时针方向依次是 2 号、3 号、……、 n 号,然后回到 1 号。由上一代猴王说出一个数字 m,从 1 号猴子开始按顺时针依次报数,报到 m 的猴子出局;再从刚出局猴子的顺时针方向下一个还在圈里的猴子开始重新从 1 开始按顺时针报数,报到 m 的猴子出局……如此重复,直至剩下一只猴子,它就成为新的猴王。

例如,当 n=5、m=3 时,依次出局的猴子序号是 3、1、5、2,最后剩下 4 号是新猴王。

有一只小猴子很想当上猴王,它想知道自己开始应该是几号才能最后成为新的猴王。

你能帮助它吗?

【输入格式】

一行,两个正整数 n、m,中间以一个空格隔开。

【输出格式】

一行,一个整数,表示小猴子想要当猴王的开始序号。

【样例1输入】

5 3

【样例1输出】

4

【样例2输入】

1234567 2333333

【样例2输出】

322345

【数据范围】

共 10 个测试点,具体如下:

测试点编号 n m
1-2 10001000 1000 1000
3-6 10710^7 107 10^7
7-10 < 2312^{31} ≤ 2