【题解】51nod1074：约瑟夫环V2

原题传送门
具体数学上看的一愣一愣的，自己瞎想了想好像明白了
假设现在有$n$个人，先是淘汰第$k$个人，剩下$(n-1)$个人是这样排列的：$k+1,k+2,...,n,1,2,...,k-2,k-1$
若是我们知道$(n-1)$个人中幸存者是$x$，那么一一映射，$n$个人的幸存者就是$(x+k)$%$n$
得到递推关系$an{s}_i=(an{s}_{i-1}+k)$%$i$，然后最终+1
但是时间复杂度为$O(n)$，不行
想到一次可以加一大堆k上去再取模，但不能加的太大导致答案出错，所以得到每次加的k的系数是$\frac{i-ans}{k}+1$
这样一堆一堆的加就没问题了
Code：

#include <bits/stdc++.h>
#define LL long long
using namespace std;

int main(){
	LL n, k, ans = 0;
	scanf("%lld%lld", &n, &k);
	for (LL i = 1; i <= n; ){
		LL x = (i - ans) / k + 1;
		if (i + x > n) x = n - i;
		if (!x) break;
		i += x;
		ans = (ans + x * k) % i;
	}
	printf("%lld\n", ans + 1);
	return 0;
}