题目描述

有n个同学围成一圈，其id依次为1~n（n号挨着1号）。

现在从1号开始报数，第一回合报到m的人就出局，第二回合从出局的下一个人开始报数，报到m^2的同学出局。

以此类推，直到最后一个回合报到m^n−1的人出局，剩下最后一个同学。

输出这个同学的编号。

输入格式
共一行，包含两个整数n和m。

输出格式
输出最后剩下的同学的编号。

数据范围
n≤15,m≤5n≤15,m≤5
输入样例：
5 2
输出样例：
5

样例

#include<iostream>
#include<cstring>
using namespace std;
int n,m;    bool st[20];
int main()
{
    cin >> n >> m;
    memset(st, false, sizeof st);
    int t = 1;
    for(int i = 1,p = n; i < n; i++,p--)//p表示剩余总人数，每次循环一次减1，
    {
        int k = 1;
        for(int j = i; j > 0; j--) 
            k = k * m % p; //k为当前位置需要删除的,报数到 m^i,取余已经循环了
        if( k == 0) k = p;
        while(true)     //遍历数组，碰到未删除的k--
        {   
            if(!st[t])
            {
                k--;
                if(k == 0)
                {   st[t] = true; break;//删除原数组中第t个，k表示剩下的人数到第k个
                }
            }
            t++;
            if(t > n)   t = 1;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        if(!st[i]) cout << i << endl;
    }
    // i <= n; 就用 cout << t; t表示最后一个删除的位置
    return 0;
}