类似约瑟夫问题的沃瑟夫

Question

沃瑟夫问题
有 n 个人排成一圈，从 1 到 n 编号。从第一个人开始依次报数（第一个人报的数是 1，下一个人报的数是 2...，当前这个人报的数字等于前面那个人报的数字加一），报数一共进行 n 轮，对于第 i (1<=i<=n) 轮，数到 i^2 的人出列，下一个人继续从 1 开始报数。结束的时候所有人都会出列。
请依次输出每一轮出列的人的编号。

输入格式
第一行一个整数 n
输出格式
输出一行，包含 n 个数，表示每一轮出列的人的编号

样例输入

10

样例输出

1 5 6 8 9 10 2 3 4 7

数据规模
对于 100% 的数据，保证 1≤n≤5000。
一下是我用循环链表来做的,样例都对。可是不知道为什么，老是超时，有没有人帮帮我qwq

#include <iostream>
using namespace std;
struct Node{
    int v;
    Node *p,*n;
}a[5010];
int n,m;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        a[i].v=i;
        if(i==n){
            a[i].n=&a[1];
        }else{
            a[i].n=&a[i+1];
        }
        if(i==1){
            a[i].p=&a[n];
        }else{
            a[i].p=&a[i-1];
        }
    }
    Node *pd=&a[n];
    int x=0,k=1;
    while(1){
        pd=pd->n;
        ++x;
        m=k*k;
        if(x==m){
            printf("%d ",pd->v);
            if(pd->n==pd){
                break;
            }else{
                Node *l=pd->p,*r=pd->n;
                l->n=r;r->p=l;
                pd->p=pd->n=NULL;
                x=0;
                pd=l;
            }
            k++;
        }
    }
    return 0;
}

Answer 1

你想一下，第i轮是不是剩余n-i+1个人，跑ii次，是不是都是固定的呀，完全可以O(n)求出呀，完全不需要ii呀。可以考虑周期，但周期我不懂啊