#P6087. [Noip十连测]约瑟夫游戏

    ID: 5340 传统题 2000ms 256MiB 尝试: 2 已通过: 1 难度: 5 上传者: 标签>难度分类普及+/提高-构造与建模逆向思考模意义不变量排序与序列处理倍增寻找边界CF1800

[Noip十连测]约瑟夫游戏

约瑟夫游戏

题目描述

nn 个人按编号 1,2,…,n1,2,\ldots,n 围成一圈,从 11 号开始按固定方向依次报数。

每轮数到 mm 时,报 1,2,…,m−11,2,\ldots,m-1 的人出局,报 mm 的人留下,再由其后一个尚未出局的人从 11 开始报数。重复这一过程,最后留下的一个人获胜。

保证 n−1n-1 是 m−1m-1 的倍数。求获胜者的原编号。

输入格式

一行两个整数 n,mn,m。

输出格式

输出一个整数,表示获胜者的编号。

样例输入1

10 10

样例输出1

10

数据范围

  • 对于 30%30\% 的数据,2≤n≤10002\le n\le1000。
  • 对于 50%50\% 的数据,2≤n≤1062\le n\le10^6。
  • 对于所有数据,2≤m≤n<263−12\le m\le n<2^{63}-1,且 (m−1)∣(n−1)(m-1)\mid(n-1)。