感觉这题被智力打击了。。
刚开始我想的是对于每个位置我们可以暴力找出最后的位置在哪里。
因为对于当前位置p, 在进行第x步操作时,
如果p % x == 1 则 p = p + x - 1
否则 p = p - 1
并且第一步只有nlogn次, 所以我们可以暴力找出p % x == 1的情况, 然后更新, 然后就被卡常惹。。
主要是存因子要2s钟, 卡常卡一辈子卡不过去。
其实我们发现每一步操作只有两种点, 一种p = p - 1, 另一种是 p = p + x - 1
那么我们将p = p - 1的不移动, 相当于整体往前移动一格, 改变哪些 p = p + x - 1的, 这样就可以了。。。。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long using namespace std; const int N = 2e6 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-); int n, a[N]; int main() {
scanf("%d", &n);
for(int i = ; i <= n; i++) a[i] = i;
int L = , R = n;
for(int i = ; i <= n; i++) {
int p = n / i * i - + L;
a[R + ] = a[p + ];
while(p - i >= ) {
a[p + ] = a[p - i + ];
p -= i;
}
L++;
R++;
}
for(int i = L; i <= R; i++) printf("%d ", a[i]);
puts("");
return ;
} /*
*/