约瑟夫环问题

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;
}