关于复读机加强版的一些小讨论

我是复读机，所以复读 EI Editorial。

本题做 \(d=6\) 的关键点是注意到 \(\omega_6^2=\omega_6-1\)。如何批量生产这种神奇等式呢。

事实上，总是可以用成 \(\phi(d)\) 个 \(d\) 阶单位根的线性组合表示出所有的 \(d\) 阶单位根，甚至这是一组最小的基底。具体怎么构造呢？

考虑构造 \(\phi(d)\) 次多项式 \(\Phi(x)=\prod_{i\perp d} (x-\omega_d^i)\)，然后注意到这一定是整系数多项式，因为我们可以直接莫反，写成： \(\Phi(x)=\prod_{p|d} \Big(\prod_t (x-\omega_d^{pt})\Big)^{\mu(p)}\)。中间就是分圆多项式 \(x^{\frac{d}{p}}-1\)，所以至少这个多项式的系数都没有虚数部分。再多注意一下这个形式可以发现这就是整系数多项式我注意不到。

所以跟常系数齐次线性递推一样，注意到 \(\Phi(\omega_d)=0\)，考虑直接计算多项式取模 \(x^k \bmod \Phi(x)\) 就可以得到一种低阶项对高阶项的线性组合表示。