Pro.ID10004 Title约瑟夫问题 Title链接http://10.20.2.8/oj/exercise/problem?problem_id=10004 AC240 Submit571 Ratio42.03% 时间&空间限制描述n个土匪行走江湖多年,专门劫富济贫,每次行动之后会给自己留一点财宝养家糊口(不行啊?!土匪也是人。土匪也有家呀)。终于有一天,他们老了,累了,于是在一个山洞里集合,决定如何分配多年来积聚的财宝。 大土匪说:所有财宝我占一半,剩下你们分吧。 众人说:凭什么! 小土匪说:所有财宝我占一半,剩下你们分吧。 众人说:白日做梦! 不大不小中土匪说:.... 众人说:痴心妄想!! 不大不小中土匪:我还没说呢....是这样的,我看咱们的东西也不多,只有300亿英镑,也不够造一艘宇宙航母。全部人平分的话,退休生活会很艰苦。不如全部留给一个幸运的人吧。好不好。 众人心里想:那个幸运的人一定是我。于是说:那个幸运的人一定不是你! 不大不小中土匪:我想出一个办法,大家围成一个圈,每个人一个编号,从1到n。即大土匪(编号1)的下一个是二土匪(编号2),二土匪的下一个是三土匪(编号3)....第n个土匪(编号n)的下一个是大土匪。然后大家选定一个正整数X。大土匪开始数1,下一个人数2....数到X的那个人,淘汰离开圈子,下一个人重新从1开始数,数到第X的那个人也被淘汰。如此循环,直到最终只剩一个人。这个人就是幸运儿。大家认为这个方案怎么样? 众土匪虽然都是本科以上的高材生,但由于平时干的都是体力活,很少动脑筋,这次也懒得动脑筋再想另一个方案了。于是方案获得通过,且附加了一个条件,凡是被淘汰者,要被枪决,以防将来向幸运儿敲竹杠打秋风拉赞助。。。。当然,枪决之前,少不了要豪饮几斤黄酒狂吞几只炸鸡翅挥泪话别英勇就义等等场景。 接下来就是紧张刺激惊心动魄扣人心弦的残暴血腥惨无人道充满江湖味道的场面(由于场面太暴力,此处被删去五万零三百二十七字)。 天亮了,不大不小中土匪拖着疲惫的身躯,眯着通红的双眼,右手拽着支票,左手拿着手枪,嘴上叼着烟斗,缓步走出山洞。风吹过,把他的头发吹乱了。风中隐约听到他喃喃自语:一帮没看过约瑟夫问题的傻波依... 输入有多个测试用例,每个测试用例占单独一行。每个测试用例有2个正整数n和x ( 0 < n < 10000000,0 < x < 10000000),分别表示土匪人数以及选定的那个数字x。n和x之间有一个空格作为分隔。 最后一个测试用例n=0 x=0,表示输入结束。 输出Description n个土匪行走江湖多年,专门劫富济贫,每次行动之后会给自己留一点财宝养家糊口(不行啊?!土匪也是人。土匪也有家呀)。终于有一天,他们老了,累了,于是在一个山洞里集合,决定如何分配多年来积聚的财宝。 大土匪说:所有财宝我占一半,剩下你们分吧。 众人说:凭什么! 小土匪说:所有财宝我占一半,剩下你们分吧。 众人说:白日做梦! 不大不小中土匪说:.... 众人说:痴心妄想!! 不大不小中土匪:我还没说呢....是这样的,我看咱们的东西也不多,只有300亿英镑,也不够造一艘宇宙航母。全部人平分的话,退休生活会很艰苦。不如全部留给一个幸运的人吧。好不好。 众人心里想:那个幸运的人一定是我。于是说:那个幸运的人一定不是你! 不大不小中土匪:我想出一个办法,大家围成一个圈,每个人一个编号,从1到n。即大土匪(编号1)的下一个是二土匪(编号2),二土匪的下一个是三土匪(编号3)....第n个土匪(编号n)的下一个是大土匪。然后大家选定一个正整数X。大土匪开始数1,下一个人数2....数到X的那个人,淘汰离开圈子,下一个人重新从1开始数,数到第X的那个人也被淘汰。如此循环,直到最终只剩一个人。这个人就是幸运儿。大家认为这个方案怎么样? 众土匪虽然都是本科以上的高材生,但由于平时干的都是体力活,很少动脑筋,这次也懒得动脑筋再想另一个方案了。于是方案获得通过,且附加了一个条件,凡是被淘汰者,要被枪决,以防将来向幸运儿敲竹杠打秋风拉赞助。。。。当然,枪决之前,少不了要豪饮几斤黄酒狂吞几只炸鸡翅挥泪话别英勇就义等等场景。 接下来就是紧张刺激惊心动魄扣人心弦的残暴血腥惨无人道充满江湖味道的场面(由于场面太暴力,此处被删去五万零三百二十七字)。 天亮了,不大不小中土匪拖着疲惫的身躯,眯着通红的双眼,右手拽着支票,左手拿着手枪,嘴上叼着烟斗,缓步走出山洞。风吹过,把他的头发吹乱了。风中隐约听到他喃喃自语:一帮没看过约瑟夫问题的傻波依... Input 有多个测试用例,每个测试用例占单独一行。每个测试用例有2个正整数n和x ( 0 < n < 10000000,0 < x < 10000000),分别表示土匪人数以及选定的那个数字x。n和x之间有一个空格作为分隔。 最后一个测试用例n=0 x=0,表示输入结束。 Output 对应每个测试用例,单独输出一行:幸运儿的编号。 Sample Input 10 7 Sample Output 9 Author 样例输入10 7 样例输出9 提示作者 |