51nod – 约瑟夫环 V2（数论）

N个人坐成一个圆环（编号为1 – N），从第1个人开始报数，数到K的人出列，后面的人重新从1开始报数。问最后剩下的人的编号。 结论：

int ans = 0; for (int i = 1; i <= n; ++i) ans = (ans + k) % i; cout << ans % n + 1 << endl;

忘了很久以前我是怎么推出来了的，然后看了讨论区发现真正取模的次数是$O(klogn)$的，然后就可以跳着算了。

ll ans = 0; for (ll i = 1, p; i < n; i += p){ if ((i - ans) % k == 0) p = max(1LL, (i - ans) / k); else p = (i - ans) / k + 1; if (i + p >= n) p = n - i; ans = (ans + p % (i + p - 1) * k % (i + p - 1)) % (i + p - 1); } cout << (ans + k) % n + 1 << endl;