vjudge链接：https://vjudge.net/problem/Gym-101955K
题目大意：给定初始人数n，步长m，求第k个被弹出的人的编号。
这题有一个非常重要的条件，那就是sum(min(m, k)) <= 2e6
因此我们可以分情况讨论。下面假设编号从0开始。
1. k < m
此时k最大为2e6。因此我们可以使用一个O(k)的方法求出答案。
设f(n, k)为初始为n个人时第k个被弹出的人。第一个被弹出的人编号显然为(m-1)
% n，从下一个人开始从0开始重新编号，问题变成了求f(n-1,
k-1)，假设其已知，那么再把结果的坐标转换回来即可。表达式为f(n, k) =
(f(n-1, k-1) + m) % n。由于k < n，因此用它求解复杂度为O(k)。
2. m <= k
此时m最大为2e6，因此我们可以使用一个O(m)的方法求出答案。
看了大佬的博客之后豁然开朗：
maskray.me/blog/2013-08-27-josephus-problem-two-log-n-solutions
这里我用自己的语言复述一下。
设第p次报数的人为y，假设这次报数y没有被弹出，那么p % m <
m-1，设下次y报数是第q次报数。显然第0到p-1次报数总共有a = floor(p /
m)个人被弹出，所以第p次报数之后总共有n - a个人，所以q = p + n -
a。第k个被弹出去的人被弹出时显然是第(k-1) * m +
m-1次报数。如果我们能用q来推出p，那么就可以一直往前推，直到p <
n，这就是这个人的编号。
整理一下，目前已知条件只有三个：
p % m < m-1
q = p + n - a
a = floor(p / m)
我们先尝试引入模数来消掉向下取整。设p = a * m + b
则已知条件转化为：
p = a * m + b (1)
b < m-1 (2)
q = p + n - a (3)
把(1)代入(3)，得q = (m-1)a + n + b
即 q - n = (m-1) a + b， b < m-1
显然就有a = floor((q - n) / (m - 1))
这样我们就用q表示了a。
将其代入(3)中，得
p = q - n + floor((q - n) / (m - 1))
通过之前提到的策略，从(k-1) * m + m-1向前推便可以推出答案。
式子第二项在递推过程中显然是指数减小的，因此不影响复杂度。所以推到答案大约需要
((k-1)*m + m-1) / n
次迭代。由于k < n，所以复杂度为O(m)
//（我不知道为什么上面的链接里的文章里说复杂度是O(log n)）
但是存在一个问题，那就是这题需要初始化为(k-1) * m + m-1，会爆long
long，要用__int128，但是这题除了gym外目前只找到hdu能交：
acm.hdu.edu.cn/showproblem.php?pid=6458
但是gym和hdu都是windows评测机，不能用__int128，而手写的_uint128
TLE了，因此这题我没有用这个方法过掉。但是由于现场赛是用linux评测机，所以在现场赛这题应该能用这个方法过。
TLE代码：
#include <iostream>
using namespace std;
#define DEBUG 0
#define ONLINE_JUDGE
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int UINT;
bool AddEqULL(ULL& lhs, ULL rhs){
static const ULL HighBit = 1ULL << 63U;
bool both = (lhs & HighBit) && (rhs & HighBit);
bool one = (lhs & HighBit) || (rhs & HighBit);
lhs += rhs;
return both || (one && !(lhs & HighBit));
}
bool SubEqULL(ULL& lhs, ULL rhs) {
bool ans = lhs < rhs;
lhs -= rhs;
return ans;
}
struct _uint128{
static const ULL ML32 = 0xffffffffULL; //mask low32
static const ULL MH32 = 0xffffffff00000000ULL;
ULL H; //Higher 64 bit
ULL L; //Lower 64 bit
_uint128() = default;
_uint128(UINT x){
*this = x;
}
_uint128(ULL _H, ULL _L){
H = _H;
L = _L;
}
explicit operator bool(){
return L || H;
}
explicit operator ULL() {
return L;
}
bool operator < (const _uint128 &rhs) const{
return H != rhs.H ? H < rhs.H : L < rhs.L;
}
_uint128& operator += (const _uint128 &rhs){
if(AddEqULL(L, rhs.L))
++H;
H += rhs.H;
return *this;
}
_uint128 operator + (const _uint128& rhs) const{
_uint128 ans = *this;
ans += rhs;
return ans;
}
_uint128& operator -= (const _uint128& rhs) {
if (SubEqULL(L, rhs.L))
--H;
H -= rhs.H;
return *this;
}
_uint128 operator - (const _uint128& rhs) const {
auto tmp = *this;
return tmp -= rhs;
}
_uint128& operator = (UINT rhs){
L = rhs;
H = 0;
return *this;
}
_uint128& operator *= (UINT rhs){
ULL tmp = (L & ML32) * rhs;
L = (L & MH32) | (tmp & ML32);
tmp >>= 32U;
bool of = AddEqULL(tmp, (L >> 32U) * rhs);
L = (L & ML32) | ((tmp & ML32) << 32U);
tmp >>= 32U;
if(of){
++tmp;
}
of = AddEqULL(tmp, (H & ML32) * rhs);
H = (H & MH32) | (tmp & ML32);
tmp >>= 32U;
if(of){
++tmp;
}
AddEqULL(tmp, (H >> 32U) * rhs);
H = (H & ML32) | ((tmp & ML32) << 32U);
return *this;
}
_uint128 operator * (UINT rhs) const{
_uint128 ans = *this;
ans *= rhs;
return ans;
}
_uint128 operator - () const{
_uint128 ans(~H, ~L);
ans += (_uint128)1;
return ans;
}
_uint128& DivEqMod(ULL& rem, UINT x){
rem = H % x;
H /= x;
rem <<= 32U;
rem += L >> 32U;
L = (L & ML32) | ((rem / x) << 32U);
rem %= x;
rem <<= 32U;
rem += L & ML32;
L = (L & MH32) | (rem / x);
rem %= x;
return *this;
}
_uint128& operator /= (UINT x) {
ULL rem;
DivEqMod(rem, x);
return *this;
}
_uint128 operator / (UINT x) const {
auto tmp = *this;
return tmp /= x;
}
_uint128& operator <<= (UINT x){
H <<= x;
H |= (L >> (64U-x));
L <<= x;
return *this;
}
_uint128 operator << (UINT x){
_uint128 ans = *this;
ans <<= x;
return ans;
}
};
//typedef LL _uint128;
int main() {
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
int T;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> T;
for (int Ti = 1; Ti <= T; ++Ti) {
LL n, m, k; //m is the length of a step, query the k_th man.
LL ans;
cin >> n >> k >> m;
if (m <= k) {
_uint128 q;
for (q = (_uint128)(k-1) * m + (m - 1); !(q < n); q = (q - n + (q - n) / (m - 1)));
ans = (ULL)q;
} else { //k < m
LL i = n - k + 1;
ans = (m-1) % i;
for (++i; i <= n; ++i) {
ans = (ans + m) % i;
}
}
cout << "Case #" << Ti << ": " << ans + 1 << endl;
}
return 0;
}另外有一个比较巧妙的方法，不需要用到__int128。我就是用这个方法过掉的这题。
大佬博客：https://www.cnblogs.com/LJHAHA/p/10854951.html
我的代码：
#include <iostream>
using namespace std;
#define DEBUG 0
#define ONLINE_JUDGE
typedef long long LL;
int main() {
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
int T;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> T;
for (int Ti = 1; Ti <= T; ++Ti) {
LL n, m, k; //m is the length of a step, query the k_th man.
LL ans;
cin >> n >> k >> m;
if (m <= k) {
if (1 == m) {
ans = k-1;
} else {
LL i = n - k + 1;
ans = (m-1) % i;
while (i < n) {
LL c = min(n - i, (i - ans + m - 2) / (m - 1));
ans += m * c;
i += c;
ans %= i;
}
}
} else { //k < m
LL i = n - k + 1;
ans = (m-1) % i;
for (++i; i <= n; ++i) {
ans = (ans + m) % i;
}
}
cout << "Case #" << Ti << ": " << ans + 1 << endl;
}
return 0;
}