题目描述

n个同学围成一圈，其id依次为1~n（n号挨着1号）。

现在从1号开始报数，第一回合报到m的人就出局，第二回合从出局的下一个人开始报数，报到m的2次方的同学出局。

以此类推，直到最后一个回合报到m的n−1次方的人出局，剩下最后一个同学。

输出这个同学的编号。

样例

输入 5 2
输出 5

(暴力模拟) $O(n^2)$

由于数据范围较小，所以直接模拟

时间复杂度分析：迭代n次，每圈n个人

Python3 代码

N = 16 #全局变量

def liver(n,m):
flag = [0]*N #初始化定长数组

p = 1 #当前这一轮的起始位置
i = 1 #第几轮
r = n #现在剩余人数
while(i<=n): #迭代n次，最后一个被删掉的人就是幸存者
    k=1#要报到的数（优化）

    j=1
    while(j<=i):
        k = k * m % r #连乘，每次乘数%n等于最后乘积%n
        j+=1
    if k==0: #特殊情况处理
        k = r

    while(True):
        if flag[p]==0:
            k-=1
            if k==0:
                flag[p] = 1
                break
        p+=1 #p只管往后移动，不管flag值
        if p>n: #保证是圆
            p=1

    i+=1
    r-=1

return p

def main():
line = input()#从键盘读入
a=line.split(‘ ‘)
n = int(a[0])
m = int(a[1])
print(liver(n,m))

if name == “main”:
main()