自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 21:26:01，当前版本为作者最后更新于2020-03-01 13:05:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

已重制，尽可能兼顾浅显易懂与严谨性地说明这题。

---

思路

我们要对 $x^n-1$ 进行因式分解，而我们知道的是 $x^n-1$ 有 $n$ 个复根，称为单位根，分别记为 $\omega_n^0,\omega_n^1,\cdots,\omega_n^{n-1}$。

也就是说：

$$x^n-1=\prod_{k=0}^{n-1}(x-\omega_n^k)$$

如果能对这 $n$ 个根进行分组，使得每一组构成的多项式都是整系数的，且不可约，那么我们就完成了此问题。

---

分圆多项式

方便后面表述，这里定义：对于复数 $z$，若 $z^n=1$，且对于任意整数 $m \ (m\in[0,n-1])$ 都有 $z^m \neq 1$，就称 $z$ 为 $n$ 次本原单位根。

定义分圆多项式 $\phi_n(x)$ 为

$$\phi_n(x)=\prod_{k=0}^{n-1}(x-\omega_n^k)^{[\gcd(n,k)=1]} $$

（即它是由所有 $n$ 次本原单位根构成的首项为 $1$ 的多项式）

对于任意 $n$ 次单位根 $z$，都存在唯一的 $d \mid n$，使得 $z$ 是 $d$ 次本原单位根。这是因为若 $z=\omega_n^k$，取 $d=\gcd(n,k)$ ，那么 $z=\omega_{n/d}^{k/d}$，$z$ 是 $n/d$ 次本原单位根。

使用这种方法来分配 $n$ 次单位根，$x^n-1$ 可以表示为分圆多项式的乘积：

$$x^n-1=\prod_{d|n}\phi_d(x) \quad \texttt{(1)}$$

然后你可能会问，$\phi_d(x)$ 怎么算？

将等式两边取对数，得

$$\ln(x^n-1)=\sum_{d|n}\ln\phi_d(x)$$

看到这个形式想到什么？没错，就是 mobius 反演。

$$\ln\phi_n(x)=\sum_{d|n}\ln(x^d-1)\mu\left(\frac nd \right) $$

再 $\exp$ 回去，结果就出来了

$$\phi_n(x)=\prod_{d|n}(x^d-1)^{\mu\left(\frac nd \right)} \quad \texttt{(2)} $$

如果想了解相关证明，还请继续往下阅读。

---

整系数的证明

先来证明个简单的：$\phi_n(x)$ 是整系数多项式。

不妨考虑将 $\texttt{(2)}$ 式中的乘积分组，将 $\mu(n/d)=1$ 的部分记为 $A(x)$，将 $\mu(n/d)=-1$ 的记为 $1/B(x)$。

显然 $A(x)$ 和 $B(x)$ 都是首项为 $1$ 的整系数多项式，且 $A(x)/B(x)$ 是一个有理系数的多项式。再加上 $B(x)$ 的首项系数为 $1$，使用 多项式除法 的计算过程中必然都是整数，所以 $\phi_n(x)$ 是整系数多项式。

---

引入：最小多项式

证明 $\phi_n(x)$ 在有理数域上的不可约性比较麻烦。我们要引入一个重要概念：最小多项式。

对于一个代数数 $\alpha$，能满足 $f(\alpha)=0$ 的、非常数的、首项为 $1$ 且次数最低的多项式称为「最小多项式」。

最小多项式有三大性质：「不可约性」、「唯一性」，以及任意以 $\alpha$ 为根的多项式都能被 $f(x)$ 整除。具体证明见 wiki 上的页面。

---

不可约性的证明

现在让我们开始吧！

考虑反证法，假设 $\phi_n(x)$ 在有理数域上可约。那么存在一个最高次项系数为 $1$ 的、非常数的、整系数不可约多项式 $f(x)$ 为 $\phi_n(x)$ 的因式。现在就可以将其写为 $\phi_n(x)=f(x)g(x)$。

然后选取 $\epsilon$ 和 $\zeta$ 分别为 $f(x)$ 和 $g(x)$ 的根（显然它们也都是 $n$ 次本原单位根）。不过我们的选取有条件，要使得 $\zeta=\epsilon^k$ 中的 $k$ 最小。
值得说明的是：固定 $\zeta$ 与 $\epsilon$ 时，这样的 $k$ 唯一存在。因为设 $\zeta=\omega_n^a$，$\epsilon=\omega_n^b$（$a,b$ 均与 $n$ 互质），那么 $a\equiv bk\pmod n$ 在 $n$ 以内有唯一解。

找出 $k$ 的最小质因子 $p$，那么有 $n\bmod p \neq 0$，所以 $\epsilon^p$ 也是 $n$ 次本原单位根。根据分解的结果，$\epsilon^p$ 要么是 $f(x)$ 的根，要么是 $g(x)$ 的根。

如果 $f(\epsilon^p)=0$，那么 $\zeta = (\epsilon^p)^{k/p}$，这说明我们选取的这组 $(\epsilon,\zeta)$ 没能使得 $k$ 最小，与假设矛盾；
所以只能是 $g(\epsilon^p)=0$。再根据假设，$k$ 已经取到最小了，那就只能有 $k=p$，即最小的 $k$ 必然是个质数。

进一步地，根据 $f(x)$ 的不可约性与 $f(\epsilon)=0$，可知 $f(x)$ 是 $\mathbb Q$ 中 $\epsilon$ 的最小多项式。由于 $g(\epsilon^p)=0$，所以 $f(x)$ 能整除 $g(x^p)$（使用引理）。

现在我们将问题转移到有限域 $\mathbb F_p$ 中。
在 $\mathbb F_p[x]$ 上的多项式 $h(x)$ 总有 $h(x)^p=h(x^p)$（这是 Lucas 定理）：

$$h(x)^p\equiv \sum_{i=0}^p\binom pi \left( \frac{h(x)-h_0}{x} \right)^{p-i} x^{p-i}h_0^i\equiv h_0^p+x^p\left( \frac{h(x)-h_0}{x} \right)^p \pmod p $$

如此展开下去计算即可证明。

然后对于整系数多项式 $f(x)$，我们记 $\bar f(x)$ 是其映射到 $\mathbb F_p[x]$ 上的结果。具体地，就是将每一项系数都对 $p$ 取模。

现在我们知道，$\bar \phi_n(x)=\bar f(x) \bar g(x)^p$。由于 $\bar f(x)$ 是 $\bar g(x)^p$ 的因式，$\bar f(x)$ 和 $\bar g(x)$ 之间必然存在一个公因式 $\bar d(x)$。现在也就是说，$\bar \phi_n(x)$ 里面有重复的因式 $\bar d(x)$，对于 $\bar F(x)$ 也会有重因式（$F(x)=x^n-1$）。

最后，我们发现 $\bar F'(x)=n x^{n-1} \neq 0$（因为 $n \bmod p \neq 0$）。按理说若 $\bar F(x)$ 有重因式，$\bar F(x)$ 与 $\bar F'(x)$ 就会有公因式 —— 但现在看来这不可能，因为 $\bar F(x)$ 没有 $0$ 作为根而 $\bar F'(x)$ 只有 $0$ 是根。这样就导出了矛盾。

即，$\phi_n(x)$ 在有理数域上是不可约的。

---

计算细节

最后是一些计算上的细节，求 $\phi_n(x)$ 时，需要进行 $2^{\omega(n)}$ 次多项式运算，每次都是 乘/除 一个形如 $x^d-1$ 的多项式，保留到 $\varphi(n)$ 次系数即可。即求 $\phi_n(x)$ 的时间复杂度为 $2^{\omega(n)}\varphi(n)$，应该没什么特别好的办法优化。

---

参考代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 10003
#define ll long long
#define p 998244353
using namespace std;

int mu[N],pr[N>>1];
bool vis[N];

struct poly{
    int a[N];
    int t;
    inline poly(int t=0):t(t){ memset(a,0,sizeof(a)); }
    inline int operator [] (const int& x) const{ return a[x]; }
    inline int& operator [] (const int& x){ return a[x]; }

    inline bool operator < (const poly& b) const{
        if(t!=b.t) return t < b.t;
        for(int i=t;~i;--i){
            if(abs(a[i])!=abs(b[i])) return abs(a[i])<abs(b[i]);
            if(a[i]!=b[i]) return a[i]<b[i];
        }
        return true;
    }

    inline void print(){
        if(abs(a[t])!=1) printf("%dx^%d",a[t],t);
        else{
            if(t==1) putchar('x');
            else printf("x^%d",t);
        }
        for(int i=t-1;i;--i){
            if(a[i]==0) continue;
            if(a[i]>0) putchar('+');
            else putchar('-');
            if(abs(a[i])!=1) printf("%dx",abs(a[i]));
            else putchar('x');
            if(i!=1) printf("^%d",i);
        }
        printf(a[0]>0?"+1":"-1");
    }
}phi[73];

void sieve(int n){
    int cnt = 0;
    mu[1] = 1;
    for(int i=2;i<=n;++i){
        if(!vis[i]){
            pr[++cnt] = i;
            mu[i] = -1;
        }
        for(int j=1;j<=cnt&&i*pr[j]<=n;++j){
            vis[i*pr[j]] = true;
            if(i%pr[j]==0){
                mu[i*pr[j]] = 0;
                break;
            }
            mu[i*pr[j]] = -mu[i];
        }
    }
}

inline void multiply(poly &f,int d){
    f.t += d;
    for(int i=f.t;i>=d;--i) f[i] = f[i-d]-f[i];
    for(int i=0;i!=d;++i) f[i] = -f[i];
}

inline poly getphi(int n){
    static poly mul,div,res;
    mul = div = poly();
    mul[0] = div[0] = 1;
    for(int d=1;d*d<=n;++d){
        if(n%d!=0) continue;
        if(mu[n/d]==1) multiply(mul,d);
        else if(mu[n/d]==-1) multiply(div,d);
        if(d*d==n) continue;
        if(mu[d]==1) multiply(mul,n/d);
        else if(mu[d]==-1) multiply(div,n/d);
    }
    if(div.t==0) return mul;
    res.t = mul.t-div.t;
    res[0] = mul[0]*div[0];
    for(int i=1;i<=res.t;++i){
        res[i] = mul[i];
        for(int j=0;j!=i;++j) res[i] -= res[j]*div[i-j];
        res[i] *= div[0];
    }
    return res;
}

int n,fc;

int main(){
    scanf("%d",&n);
    sieve(n);
    for(int i=1;i*i<=n;++i){
        if(n%i!=0) continue;
        phi[++fc] = getphi(i);
        if(i*i!=n) phi[++fc] = getphi(n/i);
    }
    if(fc==1){
        phi[1].print();
        return 0;
    }
    sort(phi+1,phi+1+fc);
    for(int i=1;i<=fc;++i){
        putchar('(');
        phi[i].print();
        putchar(')');
    }
    return 0;   
}