f(n)表示有n个人，最后一个出局的人的编号
则f(n-1)表示有n-1个人，最后一个出局的人的编号
首先这一个大圆圈，我们从0开始给他们编号，然后开始从1报数，报数到K则出局
那么第一个出局的人，他的下标编号就是K-1
有一个出局的人之后，从他的下一个开始重新给他们编号，那么就是n-1个人，刚才编号是K的现在更新他的编号是0
灵魂画师.png
0 -- 1 -- 2 -- 3 (f[n-1]，即更新后最后一个出局的人的下标编号)
k -- k+1 -- k+2 -- k+3 (最后出局的人原本的的下标编号)
那么我们就找到了 f(n-1) 和 f(n) 的一个对应关系
f(n) = (f(n-1) + k) % n
代码实现如下：
using namespace std;
const int N = 1000010;
int n, k;
int f[N];
int main()
{
f[1] = 0;
cin >> n >> k;
for(int i = 2; i <= n ; i++) f[i] = (f[i-1] + k) % i;
cout << f[n] + 1 << endl;
}
网友评论