题目内容

有 $n$ 个格子排成一列，每个格子中有数字。格子编号为 $1$ 到 $n$，初始状态下编号为 $i$ 的格子中的数字为 $i$。现在按从小到大的顺序，对于每个 $[1,n]$ 之间的整数 $x$，将所有格子编号为 $x$ 的倍数的格子中的数字循环移动一格。例如：$x = 3$ 时，将 $3$ 号格子、$6$ 号格子……$3k$ 号格子中的数字循环移动 $（3k \le n < 3k + 3）$。即 $3$ 号格子中的数字移动到 $6$ 号，$6$ 号到 $9$ 号……$3k$ 号到 $3$ 号。（移动的是格子里的数字，格子编号不变）请输出操作执行完成后每个格子里的数是多少。

输入描述

解题思路与方法

模拟操作

初始时，编号为 $i$ 的格子里存放数字 $i$。对于每个 $x=1,2,\dots,n$，要将所有编号为 $x$ 的倍数的格子中的数字循环向后移动一格。

• 令数组 arr[1…n] 存放当前各格子的数字。
• 遍历 $x$ 从 1 到 $n$：
  1. 计算该组位置个数 $k=\lfloor n/x\rfloor$。
  2. 若 $k\le1$，则无需移动。
  3. 否则，先保存最后一个位置 $k\cdot x$ 处的原值 prev = arr[k*x]，
  4. 然后从后向前依次将第 $(i-1)x$ 处的值写到 $i x$ 处（对 $i=k,k-1,\dots,2$）：