Description

开始有一初始数列 $a=[a_{1},a_{2},a_{3},···,a_{n}]$ ,定义 $f(a,k)=[a_{2},a_{3},···,a_{k},a_{1},a_{k+2},a_{k+3},···,a_{2k},a_{k+1}···]$ ，也就是把 $a$ 分段，每段 $k$ 个，若最后不足 $k$ 个时，将剩下的组成新的一段，每段第一个移成该段最后一个。

求 $f(f(f(f(f(1,2,3,···,n),2),3),···),n)$ 的结果。

$1\leq n\leq 10^{6}$ 。

Solution

考虑使用 模拟 和 找规律 来解题。

操作中是将数列按每 $k$ 个为一段，将第一个移到最后一个的位置，其他然后往前补一格。

但我们很快可以发现，有一种等价的做法是：将第 $1$ 个移到 $k+1$ 个的位置，第 $k+1$ 个移到第 $2k+1$ 的位置，一直到第 $xk+1$ 个移到 $n+1$ 的位置，第 $2$ 个到第 $n+1$ 个组成的序列和之前的做法组成的序列是一样的。

那问题就变成了在数列中移动是 $k$ 的倍数加 $1$ 的数的问题。

然后这道题目就做完了，具体细节详见代码。

Code

1

#include<cstdio>

2

int n,a[2000001],an,t;

3

int main()

4

{

5

    scanf("%d",&n);

6

    for(int i=1;i<=n;i++)

7

        a[i]=i;

8

    for(register int i=2;i<=n;i++)

9

    {

10

        an=a[i-1];

11

        for(register int j=2*i-1;j<=n+i-2;j+=i)

12

        {

13

            t=an;

14

            an=a[j];

15

            a[j]=t;

16

        }

17

        a[n+i-1]=an;

18

    }

19

    for(int i=n;i<=2*n-1;i++)

20

    {

21

        printf("%d ",a[i]);

22

    }

23

    return 0;

24

}