约瑟夫问题

任务总览

在这个问题中，你需要模拟约瑟夫问题的过程，计算出最后一个出列的人编号。该问题本质上是一个循环报数出列的问题，涉及到复杂的循环计算。

题目描述

约瑟夫问题来源于公元1世纪的犹太历史学家Josephus。问题描述如下：

有n个人（编号从1到n）围成一个圆圈，从编号为1的人开始进行1～m的正向报数，报到m的人出列。然后下一个人从下一个开始报数，直到下一个人再次报到m的人出列。这个过程不断重复，直到所有人都出列，求最后一个出列的人编号。

输入格式

输入文件仅有一行，包含两个用空格隔开的整数 N 和 M，表示总共有 N 个人和报数的步数是 M。

• 2 ≤ N ≤ 100000
• 1 ≤ M ≤ 10^9

输出格式

输出文件仅有一行，包含一个整数，表示最后一个出列的人的编号。

样例

输入数据 1

8 3

输出数据 1

7

时间复杂度分析

这个问题要求的是模拟过程中的每一步，而直接模拟可能会超时。通常我们可以使用数学公式或优化算法来求解，比如使用递归关系来快速计算出最后一个出列的编号。递归关系可以用以下公式表示：

从小到大的逐步计算可以使得该问题的计算复杂度为 O(N)，而不是 O(N*M)。