/ Vijos / 题库 /

约瑟夫问题[6]

约瑟夫问题[6]

时间限制:1秒  内存限制:256M


【问题描述】  

  YJC 很喜欢玩游戏,今天他决定和朋友们玩约瑟夫游戏。

  约瑟夫游戏的规则是这样的:\(n\) 个人围成一圈,从 1 号开始依次报数,当报到 \(m\) 时,报 \(1、2、...、m-1\) 的人出局,下一个人接着从 1 开始报,保证 \(n-1\) 是 \(m-1\) 的倍数。最后剩的一个人获胜。

  YJC 很想赢得游戏,但他太笨了,他想让你帮他算出自己应该站在哪个位置上。

【输入格式】

  第一行包含两个整数 \(n\) 和 \(m\),表示人数与数出的人数。

【输出格式】

  输出一行,包含一个整数,表示站在几号位置上能获得胜利。

【输入输出样例】

 Input

10 10

 Output

10

【数据说明】

  对于 \(30\%\) 的数据,\(2 ≤ n ≤ 1000\)。
  对于 \(70\%\) 的数据,\(2 ≤ n ≤ 1000000\)。
  对于 \(100\%\) 的数据,\(2 ≤ m ≤ n ≤ 2^{63}-1\)

【来源】

  Mr.he

信息

ID
2331
难度
9
分类
动态规划 | 递推 点击显示
标签
(无)
递交数
1
已通过
1
通过率
100%
上传者