P1520 因式分解 题解
JustinRochester
·
·
题解
传送门
双倍经验
【分析】
定义分圆多项式 \displaystyle \Phi_n(x)=\prod_{i=0}^{n-1} (x-\omega_n^i)^{[\gcd(n, i)=1]} ，其中 \omega_n^i 为 n 次单位根。
可以证明的是，所有的分圆多项式都是整数域上不可再分解的素多项式。
我们观察式子显然能发现，该分圆多项式的最高次为欧拉函数 \boldsymbol \varphi(n) ，且系数必定为 1 。
而这个式子有什么用呢？
考虑 x^n-1=0 的所有解，恰好为 \omega_n^0,\omega_n^1,\cdots, \omega_n^{n-1} 。
因此，显然有：
x^n-1&=\prod_{i=0}^{n-1}(x-\omega_n^i)
\\&=\prod_{d\mid n}\prod_{i=0}^{n-1}(x-\omega_n^i)^{[\gcd(n, i)=d]}
\\&=\prod_{d\mid n}\prod_{i=0}^{{n\over d}-1}(x-\omega_{n\over d}^i)^{[\gcd({n\over d}, i)=1]}
\\&=\prod_{d\mid n}\Phi_{n\over d}(x)
\end{aligned}
即 x^n-1 在整数域上分解为素多项式，即需要输出 n 的所有因数 d 对应的分圆多项式 \Phi_d(x) 。
分圆多项式 \Phi_n(x) 的求法则是根据上面那个式子：
x^n-1&=\prod_{d\mid n}\Phi_d(x)
\\\ln(x^n-1)&=\sum_{d\mid n}\ln \Phi_d(x)&(\text{两边取 }\ln)
\\\ln\phi_n(x)&=\sum_{d\mid n}\ln(x^d-1)\cdot \boldsymbol \mu({n\over d})&(\text{莫比乌斯反演})
\\\Phi_n(x)&=\prod_{d\mid n}(x^d-1)^{\boldsymbol \mu({n\over d})}&(\text{两边取 }\exp)
\\\Phi_n(x)&=(-1)^{\sum_{d\mid n}\boldsymbol \mu(d) }\cdot \prod_{d\mid n}(1-x^{n\over d})^{\boldsymbol \mu(d)}
\\\Phi_n(x)&=(-1)^{[n=1]}\cdot \prod_{d\mid n}(1-x^{n\over d})^{\boldsymbol \mu(d)}
\end{aligned}
考虑到 \boldsymbol \mu(d) 的取值只有 -1, 0, 1 三种，不妨分类讨论一下：
$\boldsymbol \mu(d)=1$ 时，$(1-x^{n\over d})$ 对 $\Phi_n(x)$ 的计算等价于跑一个01背包。
$\boldsymbol \mu(d)=-1$ 时，${1\over 1-x^{n\over d}}$ 对 $\Phi_n(x)$ 的计算等价于跑一个完全背包。
我们分类存储一下每个 $\boldsymbol \mu(d)$ 非零的 $d$ ，对于倍数 $kd$ 对应的分圆多项式 $\Phi_{kd}(x)$ 贡献的 $(1-x^k)$ 究竟是01背包还是完全背包。
单独把 $\Phi_1(x)$ 的符号取反一下就可以了。
设 $\omega(n)$ 表示 $n$ 的不同质因子数，则求解 $\Phi_n(x)$ 时，由于莫比乌斯函数的容斥，最多只会跑 $2^{\omega(n)}$ 次的背包，每次背包的容积又为 $\boldsymbol \varphi(n)$ 。故求解单个 $\Phi_n(x)$ 的复杂度为 $O(2^{\omega(n)}\cdot \boldsymbol \varphi(n))$ 。
故求解的总复杂度为 $O(\displaystyle \sum_{d\mid n}2^{\omega(d)}\cdot \boldsymbol \varphi(d))$ 。
由于 $\omega(n)$ 为加性函数，$\boldsymbol \varphi(n)$ 为积性函数；故 $2^{\omega(n)}$ 为积性函数；由两个积性函数的点积为积性函数，两个积性函数的迪利克雷卷积也为积性函数；故复杂度的这个函数是个积性函数，可以由线筛得出。
经过筛法求解，这个函数在 $5\times 10^3$ 范围内，最大值为 $110565$ 。
---
**【代码】**
--
注意一下多项式的排序方式和输出规范即可。
```cpp
#include <bits/stdc++.h>
using namespace std;
constexpr int Lim=1e5, MAXN=Lim+10;
int prime[MAXN], cntprime, fc[MAXN], phi[MAXN], mu[MAXN];
inline void sieve() {
phi[1]=mu[1]=1;
for(int i=2; i<=Lim; ++i) {
if(!fc[i]) {
fc[i]=prime[++cntprime]=i;
phi[i]=i-1;
mu[i]=-1;
}
for(int j=1; j<=cntprime; ++j)
if(prime[j]*i>Lim) break;
else if(prime[j]==fc[i]) {
fc[prime[j]*i]=prime[j];
phi[prime[j]*i]=prime[j]*phi[i];
mu[prime[j]*i]=0;
break;
}
else {
fc[prime[j]*i]=prime[j];
phi[prime[j]*i]=phi[prime[j]]*phi[i];
mu[prime[j]*i]=-mu[i];
}
}
}
vector<int> con[MAXN][2], d[MAXN];
inline void init() {
sieve();
for(int i=1; i<=Lim; ++i) if(mu[i])
for(int j=i, k=1; j<=Lim; j+=i, ++k)
con[j][mu[i]==1].push_back(k);
for(int i=1; i<=Lim; ++i)
for(int j=i; j<=Lim; j+=i)
d[j].push_back(i);
}
struct poly : vector<int> {
inline bool operator < (const poly &x) const {
if(size()!=x.size())
return size()<x.size();
for(int i=size()-1; i>=0; --i)
if(abs(at(i))!=abs(x[i]))
return abs(at(i))<abs(x[i]);
else if((at(i)<0)^(x[i]<0))
return at(i)<0;
return 0;
}
inline friend ostream& operator << (ostream& out, const poly &p) {
out<<"(";
for(int I=p.size()-1, i=I; i>=0; --i) {
if(p[i]==0) continue;
if(i!=I&&p[i]>0) out<<"+";
if(i==0) {
out<<p[i];
continue;
}
if(p[i]==-1) out<<"-";
else if(p[i]!=1) out<<p[i];
if(i>1) out<<"x^"<<i;
else if(i==1) out<<"x";
}
return out<<")";
}
}p[MAXN];
bool vis[MAXN];
inline void calc(int n) {
poly& phin=p[n];
phin.resize(phi[n]+1);
phin[0]=1;
for(auto e : con[n][1])
for(int i=phi[n]; i>=e; --i)
phin[i]-=phin[i-e];
for(auto e : con[n][0])
for(int i=e, I=phi[n]; i<=I; ++i)
phin[i]+=phin[i-e];
vis[n]=1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
init();
calc(1); for(auto &e : p[1]) e=-e;
int T=1, n;
while(T--&&cin>>n) {
if(n==1) {
cout<<"x-1\n";
break;
}
for(auto e : d[n])
if(!vis[e])
calc(e);
sort(d[n].begin(), d[n].end(), [](int a, int b) { return p[a]<p[b]; });
for(auto e : d[n])
cout<<p[e];
cout<<"\n";
}
cout.flush();
return 0;
}
```
---
关于双倍经验的题目（其实我是先做了双倍经验的题目再回来做这题的），由于数据范围更大，还加入了 $T$ 组数据，如果暴力跑的话可能复杂度不够。
同上文的分析，在跑满的情况下，复杂度最劣会达到 $5014548\times 100\approx 5\times 10^8$ ，复杂度比较危险。
本人的处理方式是，先 $O(n\log n)$ 预处理，把每个 $\boldsymbol \mu(d)$ 不为零的 $d$ 对倍数 $kd$ 贡献的到底是 $k$ 的01背包还是完全背包先记录下来。
后续询问的过程中，用 `vis` 数组表示这个分圆多项式的最终答案是否已经计算过了。对于每个询问的 $n$ ，我去访问它的所有因子，把它因子中没处理过的分圆多项式给算出来。
虽然最劣的复杂度和把所有分圆多项式都跑一遍没有区别，但是在随机数据的情况下会更优。
注意两题的排序方式不同。
```cpp
#include <bits/stdc++.h>
using namespace std;
constexpr int Lim=1e5, MAXN=Lim+10;
int prime[MAXN], cntprime, fc[MAXN], phi[MAXN], mu[MAXN];
inline void sieve() {
phi[1]=mu[1]=1;
for(int i=2; i<=Lim; ++i) {
if(!fc[i]) {
fc[i]=prime[++cntprime]=i;
phi[i]=i-1;
mu[i]=-1;
}
for(int j=1; j<=cntprime; ++j)
if(prime[j]*i>Lim) break;
else if(prime[j]==fc[i]) {
fc[prime[j]*i]=prime[j];
phi[prime[j]*i]=prime[j]*phi[i];
mu[prime[j]*i]=0;
break;
}
else {
fc[prime[j]*i]=prime[j];
phi[prime[j]*i]=phi[prime[j]]*phi[i];
mu[prime[j]*i]=-mu[i];
}
}
}
vector<int> con[MAXN][2], d[MAXN];
inline void init() {
sieve();
for(int i=1; i<=Lim; ++i) if(mu[i])
for(int j=i, k=1; j<=Lim; j+=i, ++k)
con[j][mu[i]==1].push_back(k);
for(int i=1; i<=Lim; ++i)
for(int j=i; j<=Lim; j+=i)
d[j].push_back(i);
}
struct poly : vector<int> {
inline bool operator < (const poly &x) const {
if(size()!=x.size())
return size()<x.size();
for(int i=size()-1; i>=0; --i)
if(at(i)!=x[i])
return at(i)<x[i];
return 0;
}
inline friend ostream& operator << (ostream& out, const poly &p) {
out<<"(";
for(int I=p.size()-1, i=I; i>=0; --i) {
if(p[i]==0) continue;
if(i!=I&&p[i]>0) out<<"+";
if(i==0) {
out<<p[i];
continue;
}
if(p[i]==-1) out<<"-";
else if(p[i]!=1) out<<p[i];
if(i>1) out<<"x^"<<i;
else if(i==1) out<<"x";
}
return out<<")";
}
}p[MAXN];
bool vis[MAXN], sorted[MAXN];
inline void calc(int n) {
poly& phin=p[n];
phin.resize(phi[n]+1);
phin[0]=1;
for(auto e : con[n][1])
for(int i=phi[n]; i>=e; --i)
phin[i]-=phin[i-e];
for(auto e : con[n][0])
for(int i=e, I=phi[n]; i<=I; ++i)
phin[i]+=phin[i-e];
vis[n]=1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
init();
calc(1); for(auto &e : p[1]) e=-e;
int T, n; cin>>T;
while(T--&&cin>>n) {
for(auto e : d[n])
if(!vis[e])
calc(e);
sort(d[n].begin(), d[n].end(), [](int a, int b) { return p[a]<p[b]; });
for(auto e : d[n])
cout<<p[e];
cout<<"\n";
}
cout.flush();
return 0;
}
```