排列==>多个环 简单的gcd、lcm关系
题目链接
https://codeforces.com/contest/1327/problem/D
题目大意
引入几个定义：
排列的乘法：如果\(a\)、\(b\)是两个排列，那么定义排列\(c=a\times b\)，其中\(\forall 1\le i\le n\ \ c[i] = b[a[i]]\)。
排列\(p\)的\(k\)次幂为：\(p^k=\underbrace{p \times p \times \dots \times p}_{k \text{ times}}\)
给定n，给定一个数字1~n的排列\(p_1,p_2,...,p_n\)，对于每个\(p[i]\)，有一个“颜色”\(c[i]\)。
“无限路径”：对于排列\(p\)，存在一个序列\(i, p[i], p[p[i]], p[p[p[i]]] \dots\)拥有相同的颜色\(c[i] = c[p[i]] = c[p[p[i]]] = \dots\)，则称排列\(p\)具有无限路径。
问：对于已知的排列\(p\)，求最小的\(k\)，使得\(p^k\)具有无限路径。
题解
问题抽象
把原始的排列\(p\)，可以看做是，节点为\(V = \{1,2,3,...,n\}\)，\(E=\big\{(i, p[i])\bigg|1\le i\le n\big\}\)有向图$G=《V,E》 $ 。由图论的知识可知，\(n\)个节点，\(n\)条边，该图的每个连通分量上有且只有一个环。而又根据排列的性质，\(p[i]\)各不相同且覆盖了所有的\(i\)，可知每个节点的入度都为1。因此，整个有向图，由多个连通分量构成，每个连通分量为一个环。
若要判断排列\(p\)是否具有“无线路径”，即看是\(G\)上是否有某个环，其中的每个节点的颜色都相等（步长为1）。
而要要判断排列\(p^k\)是否具有无线路径，即看\(G\)上是否存在某个环的某个步长为 \(k\) 的“路径”所构成的“环路”，此“环路”上的每个节点的颜色都相等。
求解
显然通过遍历的方式很容易找到所有环。现在的问题就是，对于每个环，要找一个最小的k。
设某个环的长度为\(m\)，若步长为\(k\)，则每条“k-环路”的“长度”（节点个数）为\(\frac {lcm(m,k)}k\)(\(lcm\)是最小公倍数\(least\ common\ multiple\)的简称)。而根据一个很简单但重要的公式：
\[ \forall a,b\in \mathbb{R}^+,\ \ lcm(a,b)\cdot gcd(a,b)=a\cdot b \]
每条“k-环路”的“长度”为\(\frac {lcm(m,k)}k=\frac m {gcd(m,k)}\)。
而对于一共有\(m\)个节点的环，这样的环路一共有\(m\div \frac m {gcd(m,k)}=gcd(m,k)\)个。
分析到这里，一个朴素的想法是，对每个环，从小到大验证每个k；进而对每个k，验证\(gcd(m,k)\)个“环路”，若某个环路上所有点的颜色均相同，则这个k可被接受。统计出所有可被接受的k，并求min即可。
先分析一下复杂度，对于每个环路，验证每个k需要遍历该环的所有“k-环路”，也就是遍历该环的所有节点，复杂度为\(O(m)\)，而k的可能取值为1~m（虽说k>m也有可能，但k=m必定可接受，因而k>m的情况必不是最小，无需考虑），那么验证每个环路，则需要\(O(m^2)\)的时间。那么对于全局来说，最坏情况的时间复杂度为\(O(n^2)\)，会爆TLE。
注意上一段画下划线的部分，对于k，是否所有的1~m的取值，都要考虑呢？
对于\(k_1,k_2\)，若\(gcd(k_1,m)=gcd(k_2,m)\)，则“k-环路”的“长度”是一样的，因而该环上的“k-环路”的个数也是一样的。从而每个“k-环路”上的节点也是一样的( 口胡，我不会证o(╥﹏╥)o)。故对于每个\(gcd(k,m)\)的值，我们只需要对其中最小k的验证一次即可。也就是，我们只需验证所有的m的因数k即可（对于任意k, 若m % k == 0，则gcd(k, m) = k，且对于任意一个q < k，gcd(q, m) != k = gcd(k,m)。即m的因数k，是所有gcd(ki, m) == gcd(k,m)中最小的一个ki）。
AC代码
1 |
|