约瑟夫环_牛客博客

问题描述：n个人（编号1~n)，从1开始报数，报到m的退出。按顺序输出列者编号。

时间复杂度 $O(n)$

void solve() {
    int n = read(), m = read();
    int i = 0, p;
    while (++i <= n) {
        p = i * m;
        while (p > n)
            p = p - n + (p - n - 1) / (m - 1);
        print(p);
    }
}

问题描述：n个人（编号1~n)，从1开始报数，报到m(m<<n)的退出，求胜利者的编号。

时间复杂度 $O(m)$

ll Josephus(ll n, ll m) {
    ll k = 1;
    if (m == 1)k = n;
    else {
        for (ll i = 1; i <= n; i++) {
            if ((k + m) < i) {
                ll x = (i - k + 1) / (m - 1) - 1;
                if (i + x < n) {
                    i = i + x;
                    k = (k + m * x);
                }
                else {
                    k = k + m * (n - i);
                    i = n;
                }
            }
            k = (k + m - 1) % i + 1;
        }
    }
    return k; //返回最后一人的位置
}

问题描述：n个人，1至m报数，问第k个出局的人的编号。

时间复杂度 $O(k)$

ll calc1(ll n, ll m, ll k) { // (k == n)equal(calc)
    ll p = m % (n - k + 1);
    if (p == 0) p = n - k + 1;
    for (ll i = 2; i <= k; i++) {
        p = (p + m - 1) % (n - k + i) + 1;
    }
    return p;
}

问题描述：n个人，1至m报数，问第k个出局的人的编号。

时间复杂度 $O(m∗\log(m))$

ll calc2(ll n, ll m, ll k) {
    if (m == 1) return k;
    else {
        ll a = n - k + 1, b = 1;
        ll c = m % a, x = 0;
        if (c == 0) c = a;
        while (b + x <= k) {
            a += x, b += x, c += m * x;
            c %= a;
            if (c == 0) c = a;
            x = (a - c) / (m - 1) + 1;
        }
        c += (k - b) * m;
        c %= n;
        if (c == 0) c = n;
        return c;
    }
}

共n个人，编号(1~n)，第一次出去m=1出去一个，第二次m=2出去一个，求n-1次后留下的那个人编号

时间复杂度 $O(n^2)$

const int N = 1e3 + 7;
int f[N][N];

int main() {
    for (int i = 2; i < N; i++) {
        for (int j = N - i; j > 0; j--) {
            f[i][j] = (f[i - 1][j + 1] + j) % i;
        }
    }
    int n = read();
    print(f[n][1] + 1);
    return 0;
}