#P2540. 约瑟夫环问题

约瑟夫环问题

题目描述

据说著名犹太历史学家 Josephus 有过以下的故事:在罗马人占领乔塔帕特后,3939 个犹太人与 Josephus 及他的朋友躲到一个洞中,3939 个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,4141 个人排成一个圆圈,由第 11 个人开始报数,每报数到第 33 人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。

然而 Josephus 和他的朋友并不想遵从。问题是,一开始要站在什么地方才能避免被处决?

Josephus 要他的朋友先假装遵从,他将朋友与自己安排在第 1616 个与第 3131 个位置,于是逃过了这场死亡游戏。

问题来了:

nn 个人编号 1n1 \sim n,围成一个圈,从 11 号开始,数到 mm 退出,求 nn 个人的出圈次序(每个数后面输出一个空格)。

输入格式

一行两个整数 nnmm,之间用一个空格分开。

输出格式

一行,按出圈顺序输出每个人的编号,每个数后面输出一个空格。

41 3
3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16 31 

数据范围

n<10000n < 10000m<10000m < 10000