数论--约瑟夫环及其变形

约瑟夫环： n 个人数到 k 出列，最后剩下的人编号

int main()
{
    long long n, k;
    cin >> n >> k;

    long long y = k % 2;
    long long x = 2, t = 0;
    long long z1 = y, z2 = x;
    while (x <= n)
    {
        z1 = y;
        z2 = x;
        t = (x - y) / (k - 1);
        if (t == 0)
        {
            t++;
        }
        y = y + t * k - ((y + t * k) / (x + t)) * (x + t);
        x += t;
    }

    cout << (z1 + (n - z2) * k) % n + 1 << endl;

    return 0;
}

变形一：
n个人(编号 1...n),先去掉第m个数,然后从m+1个开始报1,
报到k的退出,剩下的人继续从1开始报数.求胜利者的编号.

int main()
{
    int n, k, m;
    while (cin >> n >> k >> m, n || k || m)
    {
        int i, d, s = 0;
        for (i = 2; i <= n; i++)
        {
            s = (s + k) % i;
        }
        k = k % n;
        if (k == 0)
        {
            k = n;
        }
        d = (s + 1) + (m - k);
        if (d >= 1 && d <= n)
        {
            cout << d << '\n';
        }
        else if (d < 1)
        {
            cout << n + d << '\n';
        }
        else if (d > n)
        {
            cout << d % n << '\n';
        }
    }

    return 0;
}

变形二：
约瑟夫游戏的规则是这样的：n 个人围成一圈，从 1 号开始依次报数，当报到 m 时，报 1、2、…、m-1 的人出局，下一个人接着从 1开始报，保证(n-1)是(m-1)的倍数。最后剩的一个人获胜。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m;
ll solve(ll now,ll last)
{
    if (now==m) return now-last;         //剩下的人恰好是m个
    ll t=solve(now/m+now%m,now%m);
    return t*m-last; 
}
int main()
{
    scanf("%lld%lld",&n,&m);             //(n-1)%(m-1)==0
    printf("%lld",solve(n,0));
    return 0;
}

引用参考：约瑟夫环问题
约瑟夫环问题及其变形