题解 P1520 【因式分解】

· · 题解

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

思路

我们要对 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;   
}