Description：

$N$ 个人坐成一个圆环(编号为 $1$ ~ $N$ )，从第 $1$ 个人开始报数，数到 $K$ 的人出列，后面的人重新从 $1$ 开始报数。问最后剩下的人的编号。

$2\le n \le 10^{18},1\le k \le 1000$

Solution：

约瑟夫问题有递推式 $f[i]=(f[i-1]+k)\%i$ (用 $0$ ~ $n-1$ 标号)，发现 $k$ 很小，于是可以多次计算再取模， $f[i-1]+w\times k\le i$ ，于是一次计算 $w$ 次。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

long long n,k;

int main()

{

	long long f = 0;

	cin >> n >> k;

	for(long long i = 1;i <= n;)

	{

		long long x = (i - f) / k + 1;

		if(i + x > n)x = n - i;

		if(x == 0)break;

		f = (f + k * x) % (i + x);

		i += x;

	}

	cout << f + 1 << endl;

	return 0;

}