约瑟夫环时间超限问题(语言-c++)

Question

题目描述
n个人排成一圈，按顺时针方向依次编号1，2，3…n。从编号为1的人开始顺时针报数，报到m的人退出圈子。这样不断循环下去，圈子里的人将不断减少。最终一定会剩下一个人。试问最后剩下的人的编号。

输入
不超过1000组数据。

每组数据一行，每行两个正整数，代表人数n (1 <= n < 231)和m(1<=m<=1000)。

输出
每组输入数据输出一行, 仅包含一个整数，代表最后剩下的人的编号。

样例
7 2
2 2
7
1
为什么代码会时间超限啊，这个效率不是很高了吗？

#include <iostream>

using namespace std;

long long found(long long n,long long m)
{
    long long answer=1,i,a;
    for(i=2;i<=n;i++)
    {
        if(i>answer+m)
        {
            a=(i-answer)/m;
            if(a>n-i)
                a=n-i;
            i+=a;
            answer+=a*m;
        }
        answer=(answer+m-1)%i+1;
    }
    printf("%lld\n",answer);
    return 0;
}

int main()
{
    long long n,m;
    while(scanf("%lld%lld",&n,&m)!=EOF)
    {
        if(n<2)
            printf("1\n");
        else
            found(n,m);
    }
    return 0;
}

Answer 1

你这个是"约瑟夫环问题"，如果全使用循环会比较慢
剩下的人的编号可以通过以下公式计算可以换称这个
f(n, m) = (f(n-1, m) + m) % n
下面的代码可以自行运行测试一下

#include <iostream>
using namespace std;

int findLastPerson(int n, int m) {
    int lastPerson = 0;
    for (int i = 2; i <= n; i++) {
        lastPerson = (lastPerson + m) % i;
    }
    return lastPerson + 1;
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        cout << findLastPerson(n, m) << endl;
    }
    return 0;
}

Answer 2

该代码实现了约瑟夫环问题，即给定n个人排成一圈，按顺时针方向依次编号1，2，3...n，从编号为1的人开始顺时针报数，报到m的人退出圈子，然后继续从下一个人开始报数，直到最后只剩下一个人，求最后剩下的人的编号。

代码中的found函数用于计算最后剩下的人的编号。在循环中，通过判断i是否大于answer+m来确定是否需要跳过一些人，从而提高效率。如果需要跳过的人数a大于n-i，则将a设为n-i，以确保不会越界。然后更新i和answer的值。最后，根据计算得到的answer输出结果。

在主函数中，通过循环读取输入的数据，如果n小于2，则直接输出1，否则调用found函数计算结果。

然而，该代码的时间复杂度较高，可能导致在输入规模较大时出现时间超限的问题。需要优化算法以提高效率。