思路

• 定义数的“平方因子核”函数：记 $\mathrm{sf}(x)$ 为 $x$ 的质因子中幂次为奇数的质因子相乘得到的数（即把所有平方因子剥去后得到的平方自由部分）。

• 关键性质：对任意正整数 $a,b$，有

  $a\cdot b \text{ 是完全平方数} \iff \mathrm{sf}(a)$ = $\mathrm{sf}(b).$

• 因此，将 $1\ldots n$ 按 $\mathrm{sf}(x)$ 相等分组。组内相邻两数乘积一定为平方数；不同组之间不可能为平方数。

• 若把每个组作为一个连续块并依次拼接，则代价为所有组内成功对数之和，即

  $\sum_{G} (|G|-1)$ = $n$ - $\#\{\text{不同的 } \mathrm{sf}(x)\}.$

题目内容

给定一个正整数 $n$ ，一个长度为 $n$ 的排列 $p$ 是由 {$1,2,...,n$} 这 $n$ 个整数按任意顺序组成的数组，其中每个整数恰好出现一次;

我们定义该排列的代价为满足 $p_i×p_{i+1}$ 是完全平方数的索引 $i$ 的个数 $(1 ≤i< n)$ ;