本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-15 07:30:16

题意

给定两个排列 $A$ 与 $P$，定义一次操作表示对于所有的 $1\le i \le n$，将 $A_i$ 替换为 $A_{P_i}$。要求进行任意非负整数次操作，求能得到的字典序最小的排列。

题解

我们由 $i$ 向 $P_i$ 连一条有向边，那么可以得到一张图。考虑到现在一次操作实际上就是每个下标步进一次。

这时我们发现，确定操作次数，最终的排列就确定；换句话说，确定某一个点移动多少步，整个排列就确定。由此，结合要让字典序最小，很自然地考虑到要让每个环上的第一个位置最小。

但是这样可能冲突。考虑有两个大小为 $3$ 和 $6$ 的环，假设第一个环上移动 $2$ 步最优，第二个环上移动 $1$ 步最优。这时无论怎么操作，两个环都无法同时最优。换句话说，这两个同余方程没有公共解。

由于我们还要保证字典序最小，那么显然是尽量满足前面的环，即最小位置在最前面的环。后面的环怎么办？考虑枚举每个环上移动的步数 $k$，使得 $k$ 和前面的同余方程不冲突，在此条件下满足字典序尽可能小（即最小位置放尽可能小的数）。

怎么判断某个 $k$ 是否满足前面的同余方程？考虑到这个同余方程的模数是前面所有环长的 $\text{lcm}$，是阶乘级别的，没法直接做（然而官方题解拿 Python 水了）。考虑到

$$ x\equiv a \pmod m \Leftrightarrow x\equiv a_i\pmod {m_i^{\lpha_i}} $$

其中 $m_i, \lpha_i$ 是 $m$ 的标准分解。

那么可以分解出环长的质因子。设 $f(p)$ 表示当前同余方程的解模 $p$ 的值。那么枚举操作次数 $k$ 的同时，要满足对环长的每一个质因子 $p$，$k \bmod p$ 都和 $f(p)$ 相同。满足这个条件的情况下，再让字典序尽可能小。

于是我们做完了。

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 2e5 + 10;
int ps[N], minp[N], res[N], z[N], p[N], w[N], f[N], nr = 0;
bool vis[N];

void sieve (void)
{
	for (int i = 2; i < N; i++) {
		if (!minp[i]) ps[++nr] = i, minp[i] = i;
		for (int j = 1; ps[j] * i < N; j++) {
			minp[i * ps[j]] = ps[j];
			if (i % ps[j] == 0) break;
		}
	}
}

int main (void)
{
	int n;
	
	cin.tie (0)->sync_with_stdio (false);
	cin >> n;
	
	sieve ();
	memset (f, -1, sizeof f);
	
	for (int i = 1; i <= n; i++) cin >> w[i];
	for (int i = 1; i <= n; i++) cin >> z[i];
	for (int i = 1; i <= n; i++) if (!vis[i]) {
		int j = i;
		vector<int> q, p;
		
		while (!vis[j]) vis[j] = true, q.push_back (j), j = w[j];
		int l = q.size (), t = l;
		while (t > 1) {
			int u = minp[t], w = 1;
			while (t % u == 0) t \/= u, p.push_back (w *= u);
		}
		
		int k = -1;
		for (int i = 0; i < l; i++) {
			for (auto j : p) if (f[j] != -1 && i % j != f[j]) goto nxt;
			if (k == -1 || z[q[k]] > z[q[i]]) k = i;
			nxt:;
		}
		
		for (int i = 0; i < l; i++) res[q[i]] = z[q[(i + k) % l]];
		for (auto v : p) f[v] = k % v;
	}
	
	for (int i = 1; i <= n; i++) cout << res[i] << " \n"[i == n];
	return 0;
}