第一次把范围看成2e6，于是吓得我赶紧写FFT，后来发现FFT可以过2e6的数据，但是内存得大一点……

总共用时0.2s，一个点竟然给5s，我觉得有必要把时限限制得稍紧一些
======我是分割线=====
E,X两个字母就是用两个颜色对物体染色，物体置换群G = {转0格，转1格，...，转(n-1)格}，对于每一个置换 $g$，拆解得循环节个数为 $c(g)$，容易发现转 $k$格的置换$ g_{k} $ 的循环节个数 $ c(g_{k}) = gcd(k, n) $ 直接套用polya定理，最后答案就是
$ \frac{1}{n} \sum_{k=0}^{n-1} 2^{gcd(k, n)} $
然后我这么快的高精度运算模板都还是TLE了，于是我们对于$ \frac{1}{n} $右边的式子继续进行化简
$ \sum_{i=0}^{n-1} 2^{gcd(i, n)} $
$ = \sum_{d|n}^{ } \sum_{i=1}^{n} 2^{gcd(i, n)} [gcd(i, n) == d] $
$ = \sum_{d|n}^{ } \sum_{i=1}^{n} 2^{gcd(\lfloor \frac{i}{d} \rfloor,\lfloor \frac{n}{d} \rfloor)} [gcd(\lfloor \frac{i}{d} \rfloor,\lfloor \frac{n}{d} \rfloor) == 1] $
熟悉积性函数那套理论的同学一眼就看出了每个约数d对答案的贡献为$ 2^d \phi(\frac{n}{d})$
最后答案就是$ \frac{1}{n} \sum_{i|n}^{ } 2^i \phi(\frac{n}{i}) $
=====我是分割线=====
压位+FFT一块使用，效果惊人

这题根本目的是练习高精度......

由于cojs评测姬的速度比SGU慢，所以时限放到5S。