约瑟夫环问题

n 个人的编号是 1~n，如果他们依编号按顺时针排成一个圆圈，从编号是1的人开始顺时针报数。
（报数是从1报起）当报到 k 的时候，这个人就退出游戏圈。下一个人重新从1开始报数。
求最后剩下的人的编号。这就是著名的约瑟夫环问题。

本题目就是已知 n，k 的情况下，求最后剩下的人的编号。

当时，可以线性求解

inline ll cir(ll n, ll k) {
    ll p = 0;
    for (int i = 2; i <= n; ++i) p = (p + k) % i;
    return p + 1;
}
// f (n, k) = ( f(n − 1, k) + k ) % n
int main() {
    ll n, k;
    scanf("%lld%lld", &n, &k);
    printf("%lld\n", cir(n, k));
    return 0;
}

右边是指下一个轮次的状况：相当于起始点向右移动了k个。

#include <iostream>
using namespace std;
typedef long long ll;
// 数据范围n<=10^18,m<=1000
int main() {
    ll n, k;
    while (cin >> n >> k) {
        ll f1 = 0, f2, x;
        if (k == 1) {
            cout << n << '\n';
        } else {
            for (ll i = 2; i <= n; ++i) {
                if (f1 + k < i) {      // 表示很有可能跳过X个i
                    x = (i - f1) / k;  // 能跳过多少个
                    if (i + x < n) {   // 如果没有跳过n，就是i<=n
                        i = i + x;     // i直接到i+x
                        f2 = (f1 + x * k);  // 由于f1+x*M肯定<=i,所以这里不用%i
                        f1 = f2;
                    } else {
                        // 如果跳过了n,那么就不能直接加X了，而是只需要加(n-i)个M即可
                        f2 = f1 + (n - i) * k;
                        f1 = f2;
                        i = n;
                    }
                }
                f2 = (f1 + k) % i;
                // 如果f1+k>=i或者跳过上面的一些i之后还是要继续当前i对于的出列的人
                f1 = f2;
            }
            cout << f2 + 1 << endl;
        }
    }
    return 0;
}