$i|j$ 时，循环节长度为 $j$ 要改的字符貌似不多于长度为 $i$ 要改的字符。

所以是否能把质因子提出来，然后进行分组，使得每组的任意两个数 $a_i,a_j$（$i<j$）都满足 $a_i | a_j$，然后对每组二分，统计最小值。

瞎算了一下是 $O(n\log^2n\log\dfrac{\sqrt{n}}{\log^2n})$。