分圆多项式
分圆多项式
记$w_n$表示一个$n$次本原单位根（即$w_n^1,\ldots,w_n^{n-1}\neq 1$且$w_n^{n}=1$）。那么$w_n^1,w_n^1,\ldots,w_n^{n-1},w_n^n$是$x^n-1$的$n$个根。因此有：
\[x^n-1=\prod_{i=1}^{n}(x-w_n^i)\]定义分圆多项式为$\Phi_n(x)=\prod_{i=1}^{n}(x-w_n^i)^{[gcd(i,n)=1]}$。即根恰好为所有$n$次本原根的多项式。
由定义可以发现：
\[\prod_{d|n}\Phi_d(x)=x^n-1\]我们可以用莫比乌斯反演推出：
\[\begin{aligned} \sum_{d|n}\ln \Phi_d(x)&=\ln(x^n-1)\\ \Rightarrow \ln \Phi_n(x)&=\sum_{d|n}\mu(n/d)\ln(x^d-1)\\ \Rightarrow \Phi_n(x)&=\prod_{d|n}(x^d-1)^{\mu(n/d)}\\ \end{aligned}\]我们也可以通过递推的方式计算$\Phi_n(x)$，直接通过$(x^n-1)/\prod_{d|n\land d<n}\Phi_d(x)$来得到，其中$\Phi_1(x)=x-1$。
分圆多项式的特性如下：
- 分圆多项式都是首一整系数多项式
- 分圆多项式在整数环$\mathbb{Z}$上是不可约的
- 在$\mod \Phi_n(x)$意义下，$x$的阶正好为$n$。
题目1：计算$\Phi_n(x)$。
可以考虑两种做法，一种是通过$\Phi_n(x)=(x^n-1)/\prod_{d|n\land d<n}\Phi_d(x)$来得到。这种做法的时间复杂度为$O(\sum_{d|n}d^2)$，同时它还能对于任意$t|n$，找到$\Phi_t(x)$。
还有一种方法是通过$\Phi_n(x)=\prod_{d|n}(x^d-1)^{\mu(n/d)}$得到，利用一些技术，我们可以得到$O(n\log_2n)$的时间复杂度的算法。
题目2：对$x^n-1$做因式分解，将其分解为$f_1\times f_2\times \cdots \times f_k$的形式，且$f_i$是不可约整系数多项式。
提供一道题目。
根据下面公式找到所有分圆多项式，之后输出即可。
\[\prod_{d|n}\Phi_n(d)=x^n-1\]