最小移动距离
平面上有 $n$ 个点，编号为 $1 \sim n$。
对于每个点 $i$（$1 \leq i \leq n$），都存在一条从点 $i$ 到点 $a_i$（$1 \leq a_i \leq n$，$a_i$ 可以等于 $i$）的有向边。
所有边的长度均为 $1$。
请你判断是否存在一个最小移动距离 $t$（$t \geq 1$），使得：
- 我们规定，如果从点 $u$ 出发，移动 $t$ 单位长度距离后，到达点 $v$，就称点 $v$ 是点 $u$ 的目标点。注意，一个点的目标点也可能是它自己。
- 对于图中的每个点 $x$，如果点 $y$ 是点 $x$ 的目标点，则点 $x$ 也必须是点 $y$ 的目标点。
如果存在这样的 $t$，请你输出 $t$ 的最小可能值，否则请你输出 $-1$。
输入格式
第一行包含一个整数 $n$。
第二行包含 $n$ 个整数 $a_1,a_2, \dots ,a_n$。
输出格式
如果存在满足条件的 $t$（$t \geq 1$），则输出一个正整数，表示 $t$ 的最小可能值。
否则输出 $-1$。
数据范围
前 $3$ 个测试点满足 $1 \leq n \leq 4$。
所有测试点满足 $1 \leq n \leq 100$，$1 \leq a_i \leq n$。
输入样例1：
4 2 3 1 4
输出样例1：
3
输入样例2：
4 4 4 4 4
输出样例2：
-1
输入样例3：
4 2 1 4 3
输出样例3：
1
解题思路
首先可以发现每个点的出度都是$1$，意味着这个图是一个基环树，即一个环上挂着一堆树（也可能没有挂树，意味着此时是一个环图）。如果这个基环树挂着树，对于树中的任意一个点，它的目标结点一定会在树的父节点方向上或者在环上，但目标结点不可能在回到这个出发点，因为不存在往回走的路径。因此如果环上挂了树的话那么一定是无解。
比如红色这个点，它是树上的一个结点。从红色点出发，如果目标结点是树上的结点，由于目标结点没有往回走的路径，因此无法到达红色点。如果目标结点在环上，由于在环上的点无论这么走都只会到达环上的点，因此也无法到达红色的点。
因此如果想有解意味着必然是一堆环，环上不能挂着树。一个环上如果挂着树，意味着环上必然存在某个点的入度大于$1$，因此如果环上挂着树等价于某个点的入度大于$1$，即如果每一棵基环树上都没有挂树等价于所有点的入度都是$1$。
如果所有的连通块都是环的话必然存在解，我们可以让$t$等于所有环的长度的最小公倍数，这样的话对于环上的每一个点来说走$t$步一定可以走回到自己，但这不是最优解。考虑环长度为偶数的情况，对于环上的两个点$x$和$y$，如果从$x$走$\frac{t}{2}$步可以走到$y$，意味着从$y$走$\frac{t}{2}$步也可以走到$x$，因此对于长度为偶数的环不一定要取整个环的长度$t$，只要取长度的一半就可以了。如果环的长度是奇数那么就取整个环的长度。
求环的长度的话，由于每个环都是一个连通块，因此可以用并查集来求每个连通块的点数，由于连通块是一个环，因此连通块的点数就是环的长度。虽然这是一个有向图，但连通块是一个简单环，求环长度等价于求连通块的长度，因此可以用并查集。
还要考虑的一个问题是求最小公倍数会不会爆long long。假设把$n$拆分成$n = a_1 + a_2 + \dots + a_k$，$a_1 \sim a_k$的最小公倍数$[a_1, a_2, \dots, a_k] \leq \prod\limits_{i=1}^{k}{a_i}$。因此问题就变成了把$n$分成若干个数的和，使得这若干个数的乘积最大。这是个小学数奥问题，就是分尽可能多的$3$，最后如果不够$3$的话就发$2$。由于$n$最大取$100$，因此可以分$32$个$3$和$2$个$2$，可以发现$3^{32} \times 2^2$是不会爆long long的。
证明如下：
这道题目是数学中一个很经典的问题。
下面我们给出证明：首先把一个正整数 $N$ 拆分成若干正整数只有有限种拆法，所以存在最大乘积。
假设 $N = n_1 + n_2 + \dots + n_k$，并且 $n_1 \times n_2 \times \dots \times n_k$是最大乘积。显然 $1$ 不会出现在其中；
如果对于某 $i$ 有 $n_i \geq 5$，那么把 $n_i$ 拆分成 $3+(n_i−3)$，我们有 $3(n_i−3)=3n_i−9>n_i$；
如果 $n_i=4$，拆成 $2+2$ 乘积不变，所以不妨假设没有 $4$；
如果有三个以上的 $2$，那么 $3 \times 3 > 2 \times 2 \times 2$，所以替换成3乘积更大；
综上，选用尽量多的 $3$，直到剩下 $2$ 或者 $4$ 时，用 $2$。
AC代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 typedef long long LL;
5
6 const int N = 110;
7
8 int d[N], fa[N], cnt[N];
9
10 int find(int x) {
11 return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
12 }
13
14 LL gcd(LL a, LL b) {
15 return b ? gcd(b, a % b) : a;
16 }
17
18 int main() {
19 int n;
20 cin >> n;
21 for (int i = 1; i <= n; i++) {
22 fa[i] = i;
23 cnt[i] = 1;
24 }
25 for (int i = 1; i <= n; i++) {
26 int x;
27 scanf("%d", &x);
28 d[x]++;
29 int a = find(i), b = find(x);
30 if (a != b) {
31 cnt[b] += cnt[a];
32 fa[a] = b;
33 }
34 }
35
36 for (int i = 1; i <= n; i++) {
37 if (d[i] > 1) { // 某个基环树环上挂着树
38 printf("-1");
39 return 0;
40 }
41 }
42
43 LL ret = 1;
44 for (int i = 1; i <= n; i++) {
45 if (fa[i] == i) {
46 int t = cnt[i];
47 if (t % 2 == 0) t >>= 1; // 如果环的长度是偶数则取长度的一半
48 ret = ret / gcd(ret, t) * t;
49 }
50 }
51 printf("%lld", ret);
52
53 return 0;
54 }
参考资料
AcWing 4626. 最小移动距离（AcWing杯 - 周赛）：https://www.acwing.com/video/4461/
LeetCode 343. Integer Break：https://www.acwing.com/solution/content/368/
标签：环上,int,最小,距离,times,leq,如果,长度,移动 From： https://www.cnblogs.com/onlyblues/p/16771113.html