我的群论好拉/kk
首先如果直接对着矩阵转置做显然不太能做，再加上它给出的是二的幂次，所以我们可以考虑从二进制下手。
写成二进制以后它的变化方式就明朗的多：将一个长度为 \(a+b\) 的二进制数循环位移 \(a\) 位。
众所周知这种交换题最小次数是 \(n-\) 环的个数，因此我们只需要求出环的个数即可。
这相当于求本质不同的二进制串数量，不妨令 \(\gcd(a,b)=1\)，考虑 Burnside 引理，我们只需要求出这样旋转 \(0\sim a+b-1\) 次的不动点个数即可。
这个问题再度抽象起来，但是我们考虑，这样旋转总共只能旋转出 \(a+b\) 种本质不同的串，而现在旋转的这些次数中不可能有本质相同，因此每种旋转唯一对应了向右循环 \(i\) 位。
那么事情就变得简单起来，答案即为 \(\sum\limits_{i=0}^{a+b-1}{m^{\gcd(a+b,i)}}\)，其中 \(m=\gcd(a,b)\)，这里面的 \(a,b\) 是最初的 \(a,b\) ，计算式中的 \(a,b\) 是互质的 \(a.b\)。然后枚举 \(\gcd\) 可以得到 \(\sum\limits_{d\mid n}{m^{d}\varphi(\frac{n}{d})}\)，就可以 \(O(\sqrt {a+b})\) 单组询问了。
因此总复杂度 \(O(T\sqrt {a+b})\)
标签：Even,gcd,二进制,SP422,TRANSP2,个数,sqrt,旋转,More From： https://www.cnblogs.com/275307894a/p/17399962.html