A
简单
B
简单
C
每次选一对，最大的放后面，最小的放前面，问排序好一个排列的最小次数。
考虑没有动过的那些数，它们一定是一个上升子序列，且满足 \(a_{k_i}=a_{k_{i-1}}+1\)。
对于其它动过的那 \(c\) 个数，容易在 \(\lceil\frac{c}{2}\rceil\) 次之内将它们排好序
操作不可逆的最小次数排序问题，可以考虑没有操作过的那些数
D
定义两个排列的乘法（复合）为 \(c=a\cdot b\)，\(c_i=b_{a_i}\)，给定 \(n\) 个长度为 \(m\) 的排列，对于每个排列 \(p_i\) 需要找出一个排列 \(p_j\)，使得 \(p_i \cdot p_j\) 的美丽度最大，定义一个排列 \(q\) 的美丽度为一个最长的前缀的长度，满足 \(q_i=i\)。
考虑一个已知排列 \(a\) 复合上另一个排列 \(b\) 后，美丽度为 \(k\) 时对 \(b\) 的要求，容易发现要求为 \(\forall i\in[1,k],b_{a_i}=i\)。就是对于 \(b\) 的一些位置，要求固定为某些数。
这并不是一个很好 check 的条件，注意到要求的数为 \([1,k]\)，所有考虑排列的逆排列，要求变成了对于前 \(i\) 个位置，满足 \(b'_i=a_i\)，这是一个容易检查的条件。
参考 排列变换总结 中的定义。
E
题意转化为对每个 \(m=m_1\cdot m_2\) 的约数 \(d\)，求出其最大的不超过 \(n\) 的约数。
约数的约数，级别还是挺大的，对于 \(10^{18}\) 的数，可能达到了 \(10^8\) 级别，不能暴力枚举，\(10^{18}\) 内的最大约数个数约为 \(10^5\) 个。
考虑一个约数的最大的不超过 \(n\) 的约数，它显然也是 \(m\) 的一个约数，考虑以一种类似动态规划的方式递推，枚举一个约数的所有质因数，从它们各自的最大约数转移过来，显然这是对的。