https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/description/

社团共有 num 位成员参与破冰游戏，编号为 0 ~ num-1。成员们按照编号顺序围绕圆桌而坐。社长抽取一个数字 target，从 0 号成员起开始计数，排在第 target 位的成员离开圆桌，且成员离开后从下一个成员开始计数。请返回游戏结束时最后一位成员的编号。

示例 1：

输入：num = 7, target = 4
输出：1

示例 2：

输入：num = 12, target = 5
输出：0

提示：

• 1 <= num <= 10^5
• 1 <= target <= 10^6

0 1 2 3 4 5 6

0 1 2 4 5 6

1 2 4 5 6

1 2 4 6

1 2 6

1 2

1

方法一：数学 + 递归 思路

题目中的要求可以表述为：给定一个长度为 num 的序列，每次向后数 target 个元素并删除，那么最终留下的是第几个元素？

这个问题很难快速给出答案。但是同时也要看到，这个问题似乎有拆分为较小子问题的潜质：如果我们知道对于一个长度 num - 1 的序列，留下的是第几个元素，那么我们就可以由此计算出长度为 num 的序列的答案。

算法

我们将上述问题建模为函数 f(num, target)，该函数的返回值为最终留下的元素的序号。

首先，长度为 num 的序列会先删除第 target % num 个元素，然后剩下一个长度为 num - 1 的序列。那么，我们可以递归地求解 f(num - 1, target)，就可以知道对于剩下的 num - 1 个元素，最终会留下第几个元素，我们设答案为 x = f(num - 1, target)。