置换和轮换（续：对其幂的讨论）

回到最初我们给出的结论：

$T^k=e$，那么k的最小整数解就是$T$的长度

这个就非常好理解了：$gcd(L_T,L_T)=L_T$

当L与k互质时

之前我们得到了一些长度与k之间的结论
其中，当$gcd(L,k)!=1$时，我们是可以直接构造出结果轮换的
下面我们就讨论一下当$L$与$k$互质时的结果轮换

举个例子：

继续：

我们可以发现，把$(mod)k=1,2,...,k-1,0$的项提出来，连接起来则是所求新轮换

定理

设$a=T,a'=T^k$，且 $gcd(L_T,k)=1$，则$a'[i]=a[(k+1)*i(mod)L_T]$

我们用图直观理解一下：
$L=10,k=3$

这是一个很有用的结论，我们把ta转化成code：

for 原置换中的每一个轮换for 环中每一个未标记元素{做标记放入结果数组前进k步until 回到此元素将结果数组中的元素取出，得到的环就是目标置换包含的一个轮换}

这个算法总结了上述三个结论和一个定理

置换的分数幂（开方）

之前我们讨论了轮换的乘方运算
下面我们就讨论开方运算：

轮换长度与指数互质：

有之前的定理可以得到，开方运算是乘方的逆：
由目标轮换构造原轮换：每次原函数指针后移$k$位，目标函数指针依次后移

轮换长度与指数不互质：

这种情况是无法开方的：

• 结果置换只包含一个轮换：
  假设我们由一个初始轮换$T$，开k次方，得到一个目标轮换$t$
  由一开始得到结论可知：$t^k=T',gcd(L_t,k)!=1$
  按理说得到的$T'$应该包含$gcd(L_t,k)$个轮换，与题设不符
  因此不可开方

  • 结果置换包含若干轮换
    结果置换的$k$次幂只有可能把自己包含的轮换分裂，不可能合并成一个大轮换

  因此，轮换长度与指数不互质时，单个轮换不能看房

  多个轮换的分数幂

  当轮换的长度与指数不互质时，会分裂成$gcd(L,k)$个轮换
  那么如果我们可以把这些轮换合并起来就可以得到初始轮换了

  $k=2$
  

  上图体现了两种开方方式：
  上图是把两个轮换交错结合
  下图是：结果轮换$T^k$的指针$i$依次后移，而需要构造的轮换的指针$j$依次后移$k$位，$T[j]=T^k[i]$

  那么我们要开$k$次方，需要将k个长度相等的轮换合并吗？
  实际上并不需要：
  如果我们选择$m$个轮换进行合并，得到的大轮换长度为$L*m$
  如果$gcd(L*m,k)=m$，就可以保证次方法正确
  显然，m是k的一个约数，并且$gcd(L,k/m)=1$
  这个式子的充要条件是：$m$为$gcd(L,k)$的倍数
  因此：$min(m)=gcd(L,k)$

  我们可以将上面两种情况并在一起：

  • $m=gcd(L,k)$
  • 选择n*m份长度为1的轮换交错合并，n为整数，且$gcd(n*m,k/m)=1$
  • 将大轮换开$k/m$次方

  将原置换中的轮换按照size排序
  for 每一个轮换m=gcd(l,k)if 有m个相同长度的轮换将m个轮换交错的输出到目标数组，保存为一个轮换将得到的大轮换开k/m次方else 无解