codeforces gym 102114 C Call It What You Want
shadowice1984
2019-02-21 20:18:49
这场gym的题目名称肥肠有趣啊，每一道题都是一首歌的名字
这首应该是老霉的 Call It What You Want ……(恕我直言reputation这张专有点炸逼但是还是能听的)
__________________________
## 前置芝士：莫比乌斯反演
阅读本题解前请确保您精通莫比乌斯反演的常见套路
我们会使用一个不标准的记号
$$\epsilon(a,b)=[gcd(a,b)==1]$$
换句话说函数$\epsilon(a,b)$表示a和b是否是互质的
# 本题题解
题目意思简单易懂，定义$\Phi(d,x)$是满足一下隐性递归式的**多项式**
$$x^n-1=\prod_{d|n}\Phi(d,x)$$
现在输入一个$n$要求对于每一个$n$的每一个约数$d$输出$\Phi(d,x)$这个多项式
好了我们来看一眼那个隐性递归式，我们发现这东西很像$id=\phi×1$
虽然上面的式子可以当做莫比乌斯反演的常用结论之一记住不过我们还可以从另一个角度理解下面这个式子
$$n=\sum_{d|n}\phi(d)$$
等号左边是分母为n的真分数的数量,等号右边则是在枚举这些真分数约分之后的分母是谁，因为约分之后的分数一定是个最简分数，所以$\phi(d)$是以分母为d的最简真分数的数目
那么说了这些有什么用呢？
我们来考虑这个式子
$$x^n-1=\prod_{d|n}\Phi(d,x)$$
我们将等式左侧因式分解，可以得到这个式子
$$\prod_{i=0}^{n-1}(x-\omega_{n}^{i})=\prod_{d|n}\Phi(d,x)$$
其中$\omega_{n}^{i}$表示n次单位根
那么我们发现对于单位根来讲有一个消去引理
$$w_{nd}^{id}=w_{n}^{i}$$
换句话说单位根和分数一样可以“约分”
那么我们不妨仿照上面的证明过程构造多项式，显然等号左侧和右侧的多项式零点必须相等,那么我们需要做的就是把这些$x-\omega_{n}^{d}$合理的塞到$\Phi(d,x)$当中,我们就能成功构造出多项式来了，经过一番构造我们得到了这样的式子
$$\Phi(d,x)=\prod_{i=1}^{d}(x-\omega_{d}^{i})^{\epsilon(d,i)}$$
换句话说我们还是枚举单位根约分之后的分母是谁，对于每一个分母我们仅仅考虑最简分数，如此这般处理就得到了上面的式子
那么我们考虑把这个式子拿过去反演一波，使用莫比乌斯反演当中最最最常用的等式，我们可以得到
$$\epsilon(d,i)=\sum_{t|d,t|i}\mu(t)$$
$$\Phi(d,x)=\prod_{i=1}^{d}(x-\omega_{d}^{i})^{\sum_{t|d,t|i}\mu(t)}$$
众所周知指数上面的$\Sigma$可以放到外面变成$\Pi$
$$\Phi(d,x)=\prod_{i=1}^{d}\prod_{t|d,t|i}(x-\omega_{d}^{i})^{\mu(t)}$$
接下来是喜闻乐见的交换$\prod$环节啦~
$$\Phi(d,x)=\prod_{t|d}\prod_{i=1,t|i}^{d}(x-\omega_{d}^{i})^{\mu(t)}$$
根据积之幂等于幂之积我们可以把$\mu(t)$移到$\Pi$外面
$$\Phi(d,x)=\prod_{t|d}(\prod_{i=1,t|i}^{d}(x-\omega_{d}^{i}))^{\mu(t)}$$
接下来我们需要令$i/=t$，那么之前式子当中的$i$都需要使用$it$来代换
$$\Phi(d,x)=\prod_{t|d}(\prod_{i=1}^{d/t}(x-\omega_{d}^{it}))^{\mu(t)}$$
由于消去引理的存在，我们可以把单位根约分
$$\Phi(d,x)=\prod_{t|d}(\prod_{i=1}^{d/t}(x-\omega_{d/t}^{i}))^{\mu(t)}$$
接下来我们把这个公式带入其中
$$x^n-1=\prod_{i=1}^{n}(x-\omega_{n}^{i})$$
就得到了这个优美的式子
$$\Phi(d,x)=\prod_{t|d}(x^{d/t}-1)^{\mu(t)}$$
~~口胡证明:因为~~$id=\phi × 1$~~，所以~~$\phi=\mu × id$
接下来我们考虑这个式子有什么性质可以让我们利用，我们不妨考虑这个式子中$\mu(t)$不等于0的部分,假设这个d的唯一分解是
$$d=\prod_{p \in primie}p^{e_{p}}$$
那么我们的$\prod$就相当于枚举了$e_{p}$不是0的p的集合的一个子集，也就是d的本质不同质因子集合的一个子集,计算这个子集的乘积t之后对于答案贡献一个$(x^{d/t}-1)^{\mu(t)}$
那么我们不妨构造一个数论函数$unique(d)$
$$unique(d)=\prod_{p \in prime}p^{[e_{p} \ne 0]}$$
也就是d的本质不同质因子的乘积，这个函数可以大力线性筛求出
**注意，下面的篇幅介绍了一个非正解做法，正解比下面的做法简单，如果只关心正解而不想提高人类智慧的话可以直接翻到下面去**
那么我们发现上面式子中的$d/t$都是$d/unique(d)$的倍数
也就是说我们可以获得一个重要性质
$$\Phi(d,x)=\Phi(unique(d),x^{d/unique(d)})$$
那么我们仅仅需要考虑$\mu(d)$不是0的多项式，别的多项式都可以简单从$\mu(d)$非0的多项式构造出来
如果你接着编下去你可以得到这样一个式子，如果$(p,Q)$互质并且$p$是一个质数，我们可以得到这样一个递推式
$$\Phi(pQ,x)=\frac{\Phi(Q,x^{p})}{\Phi(Q,x)}$$
使用ntt插值代替多项式求逆(因为我们知道除出来一定不会是一个无穷多项式)并且使用基8优化的ntt,我们可以在$O(nlogn)$的时间内通过本题，尽管这题的$n$是恐怖的$5×10^6$,这也从一个侧面展示了多项式+指令集带来的无限可能性，因为这东西常数实在是太小了
(需要使用pragma GCC target("avx2")，也就是wc上被普及的司令集)
这里给出一个范例代码，基8ntt是我扒的板子……
想看正解的可以跳过这段代码~
```C
#pragma GCC target ("avx2")
#define __AVX__ 1
#define __AVX2__ 1
#define __SSE__ 1
#define __SSE2__ 1
#define __SSE2_MATH__ 1
#define __SSE3__ 1
#define __SSE4_1__ 1
#define __SSE4_2__ 1
#define __SSE_MATH__ 1
#define __SSSE3__ 1
#include <immintrin.h>
#include<bits/stdc++.h>
using namespace std;
typedef unsigned char U8;
typedef int I32;
typedef unsigned int U32;
typedef long long I64;
typedef unsigned long long U64;
const int P=998244353;
const int inv2=(P+1)>>1;
const int G=3;
const int GInv=332748118;
const int MaxExp=22;
const int MAXN=1048576<<1;
const int MAXK=500005;
const int BmM=288737297;
const int BmW=29;
namespace NTT{
U32 GcdEx(U32 A, U32 B, I32& x, I32& y) {
if (!B) {
x = 1;
y = 0;
return A;
}
U32 d = GcdEx(B, A % B, y, x);
y -= x * (I32) (A / B);
return d;
}
inline U32 MNorm(I32 V) {
V = V % P;
return (U32) (V < 0 ? V + P : V);
}
inline U32 MAdd(U32 A, U32 B) {
U32 res = A + B;
return res < P ? res : res - P;
}
inline U32 MSub(U32 A, U32 B) {
U32 res = A - B;
return A < B ? res + P : res;
}
inline U32 MMul(U32 A, U32 B) {
return (U32) ((U64) A * B % P);
}
inline U32 MPow(U32 A, U32 B) {
U32 res = 1;
while (B) {
if (B & 1)
res = MMul(res, A);
A = MMul(A, A);
B >>= 1;
}
return res;
}
inline U32 MInv(U32 N) {
I32 x, y;
GcdEx(N, P, x, y);
x %= P;
return (U32) (x < 0 ? x + P : x);
}
inline __m256i VLod(const U32* __restrict__ A) {
return _mm256_load_si256((const __m256i*) A);
}
inline void VSto(U32* __restrict__ A, __m256i v) {
_mm256_store_si256((__m256i*) A, v);
}
inline __m256i VEx0(__m256i v) {
const __m256i vm0 = _mm256_set_epi64x(
0x111111111b1a1918, 0x1111111113121110,
0x111111110b0a0908, 0x1111111103020100
);
return _mm256_shuffle_epi8(v, vm0);
}
inline __m256i VEx1(__m256i v) {
const __m256i vm1 = _mm256_set_epi64x(
0x111111111f1e1d1c, 0x1111111117161514,
0x111111110f0e0d0c, 0x1111111107060504
);
return _mm256_shuffle_epi8(v, vm1);
}
inline __m256i VIntlv(__m256i v0, __m256i v1) {
return _mm256_blend_epi32(v0, _mm256_shuffle_epi32(v1, 0xb1), 0xaa);
}
inline __m256i VAdd(__m256i va, __m256i vb) {
const __m256i vm32 = _mm256_set1_epi32(P);
__m256i vra = _mm256_add_epi32(va, vb);
__m256i vrb = _mm256_sub_epi32(vra, vm32);
return _mm256_min_epu32(vra, vrb);
}
inline __m256i VSub(__m256i va, __m256i vb) {
const __m256i vm32 = _mm256_set1_epi32(P);
__m256i vra = _mm256_sub_epi32(va, vb);
__m256i vrb = _mm256_add_epi32(vra, vm32);
return _mm256_min_epu32(vra, vrb);
}
inline __m256i VMul(__m256i va0, __m256i va1, __m256i vb0, __m256i vb1) {
const __m256i vm32 = _mm256_set1_epi32(P);
const __m256i vm64 = _mm256_set1_epi64x(P);
const __m256i vbmm = _mm256_set1_epi64x(BmM);
__m256i vmul0 = _mm256_mul_epi32(va0, vb0);
__m256i vmul1 = _mm256_mul_epi32(va1, vb1);
__m256i vlow = VIntlv(vmul0, vmul1);
__m256i vquo0 = _mm256_srli_epi64(_mm256_mul_epi32(_mm256_srli_epi64(vmul0, 29), vbmm), BmW);
__m256i vquo1 = _mm256_srli_epi64(_mm256_mul_epi32(_mm256_srli_epi64(vmul1, 29), vbmm), BmW);
__m256i vval0 = _mm256_mul_epi32(vquo0, vm64);
__m256i vval1 = _mm256_mul_epi32(vquo1, vm64);
__m256i vval = VIntlv(vval0, vval1);
__m256i vra = _mm256_sub_epi32(vlow, vval);
__m256i vrb = _mm256_add_epi32(vra, vm32);
__m256i vrc = _mm256_sub_epi32(vra, vm32);
__m256i vmin = _mm256_min_epu32(vra, vrb);
return _mm256_min_epu32(vmin, vrc);
}
inline __m256i VMul(__m256i va, __m256i vb0, __m256i vb1) {
return VMul(VEx0(va), VEx1(va), vb0, vb1);
}
inline __m256i VMul(__m256i va, __m256i vb) {
return VMul(va, VEx0(vb), VEx1(vb));
}
inline void VMul(U32* __restrict__ A, U32 Len, U32 W) {
if (Len < 8) {
for (U32 i = 0; i < Len; ++i)
A[i] = MMul(A[i], W);
return;
}
__m256i vw = _mm256_set1_epi64x(W);
for (U32 i = 0; i < Len; i += 8)
VSto(A + i, VMul(VLod(A + i), vw, vw));
}
inline void VMul(U32* __restrict__ A, const U32* __restrict__ B, U32 Len) {
if (Len < 8) {
for (U32 i = 0; i < Len; ++i)
A[i] = MMul(A[i], B[i]);
return;
}
for (U32 i = 0; i < Len; i += 8)
VSto(A + i, VMul(VLod(A + i), VLod(B + i)));
}
inline void VSqr(U32* __restrict__ A, U32 Len) {
if (Len < 8) {
for (U32 i = 0; i < Len; ++i)
A[i] = MMul(A[i], A[i]);
return;
}
for (U32 i = 0; i < Len; i += 8) {
__m256i va = VLod(A + i);
__m256i v0 = VEx0(va);
__m256i v1 = VEx1(va);
VSto(A + i, VMul(v0, v1, v0, v1));
}
}
U32 WbFwd[MaxExp + 1];
U32 WbInv[MaxExp + 1];
U32 LenInv[MaxExp + 1];
inline void NttInitAll(int Max) {
for (int Exp = 0; Exp <= Max; ++Exp) {
WbFwd[Exp] = MPow(G, (P - 1) >> Exp);
WbInv[Exp] = MPow(GInv, (P - 1) >> Exp);
LenInv[Exp] = MInv(1u << Exp);
}
}
inline void NttImpl1(U32* __restrict__ A, U32 Len) {
for (U32 j = 0; j < Len; j += 2) {
U32 a0 = MAdd(A[j + 0], A[j + 1]);
U32 b0 = MSub(A[j + 0], A[j + 1]);
A[j + 0] = a0;
A[j + 1] = b0;
}
}
inline void NttFwd2(U32* __restrict__ A, U32 Len, U32 Wn) {
for (U32 j = 0; j < Len; j += 4) {
U32 a0 = MAdd(A[j + 0], A[j + 2]);
U32 a1 = MAdd(A[j + 1], A[j + 3]);
U32 b0 = MSub(A[j + 0], A[j + 2]);
U32 b1 = MSub(A[j + 1], A[j + 3]);
A[j + 0] = a0;
A[j + 1] = a1;
A[j + 2] = b0;
A[j + 3] = MMul(b1, Wn);
}
}
inline void NttFwd3(U32* __restrict__ A, U32 Len, U32 Wn) {
U32 W2 = MMul(Wn, Wn);
U32 W3 = MMul(W2, Wn);
const __m128i vm32 = _mm_set1_epi32(P);
for (U32 j = 0; j < Len; j += 8) {
__m128i va = _mm_load_si128((const __m128i*) (A + j));
__m128i vb = _mm_load_si128((const __m128i*) (A + j + 4));
__m128i vc = _mm_add_epi32(va, vb);
__m128i vd = _mm_sub_epi32(va, vb);
__m128i ve = _mm_sub_epi32(vc, _mm_andnot_si128(_mm_cmpgt_epi32(vm32, vc), vm32));
__m128i vf = _mm_add_epi32(vd, _mm_and_si128(_mm_cmpgt_epi32(vb, va), vm32));
_mm_store_si128((__m128i*) (A + j), ve);
_mm_store_si128((__m128i*) (A + j + 4), vf);
A[j + 5] = MMul(Wn, A[j + 5]);
A[j + 6] = MMul(W2, A[j + 6]);
A[j + 7] = MMul(W3, A[j + 7]);
}
}
inline void NttFwd(U32* __restrict__ A, int Exp) {
U32 Len = 1u << Exp;
U32 Wn = WbFwd[Exp];
for (int i = Exp - 1; i >= 3; --i) {
U32 ChkSiz = 1u << i;
U32 tw2 = MMul(Wn, Wn);
U32 tw3 = MMul(tw2, Wn);
U32 tw4 = MMul(tw3, Wn);
U32 tw5 = MMul(tw4, Wn);
U32 tw6 = MMul(tw5, Wn);
U32 tw7 = MMul(tw6, Wn);
U32 twn = MMul(tw7, Wn);
__m256i vw32 = _mm256_set_epi32(tw7, tw6, tw5, tw4, tw3, tw2, Wn, 1);
__m256i vwn = _mm256_set1_epi64x(twn);
for (U32 j = 0; j < Len; j += 2u << i) {
U32* A_ = A + j;
U32* B_ = A_ + ChkSiz;
__m256i vw = vw32;
for (U32 k = 0; k < ChkSiz; k += 8) {
__m256i va = VLod(A_ + k);
__m256i vb = VLod(B_ + k);
__m256i vw0 = VEx0(vw);
__m256i vw1 = VEx1(vw);
__m256i vc = VAdd(va, vb);
__m256i vd = VSub(va, vb);
VSto(A_ + k, vc);
VSto(B_ + k, VMul(vd, vw0, vw1));
vw = VMul(vw0, vw1, vwn, vwn);
}
}
Wn = MMul(Wn, Wn);
}
if (Exp >= 3) {
NttFwd3(A, Len, Wn);
Wn = MMul(Wn, Wn);
}
if (Exp >= 2)
NttFwd2(A, Len, Wn);
if (Exp)
NttImpl1(A, Len);
}
inline void NttInv2(U32* __restrict__ A, U32 Len, U32 Wn) {
for (U32 j = 0; j < Len; j += 4) {
U32 a0 = A[j + 0];
U32 a1 = A[j + 1];
U32 b0 = A[j + 2];
U32 b1 = MMul(A[j + 3], Wn);
A[j + 0] = MAdd(a0, b0);
A[j + 1] = MAdd(a1, b1);
A[j + 2] = MSub(a0, b0);
A[j + 3] = MSub(a1, b1);
}
}
inline void NttInv3(U32* __restrict__ A, U32 Len, U32 Wn) {
U32 W2 = MMul(Wn, Wn);
U32 W3 = MMul(W2, Wn);
const __m128i vm32 = _mm_set1_epi32(P);
for (U32 j = 0; j < Len; j += 8) {
A[j + 5] = MMul(Wn, A[j + 5]);
A[j + 6] = MMul(W2, A[j + 6]);
A[j + 7] = MMul(W3, A[j + 7]);
__m128i va = _mm_load_si128((const __m128i*) (A + j));
__m128i vb = _mm_load_si128((const __m128i*) (A + j + 4));
__m128i vc = _mm_add_epi32(va, vb);
__m128i vd = _mm_sub_epi32(va, vb);
__m128i ve = _mm_sub_epi32(vc, _mm_andnot_si128(_mm_cmpgt_epi32(vm32, vc), vm32));
__m128i vf = _mm_add_epi32(vd, _mm_and_si128(_mm_cmpgt_epi32(vb, va),vm32));
_mm_store_si128((__m128i*) (A + j), ve);
_mm_store_si128((__m128i*) (A + j + 4), vf);
}
}
inline void NttInv(U32* __restrict__ A, int Exp) {
if (!Exp)
return;
U32 Len = 1u << Exp;
NttImpl1(A, Len);
if (Exp == 1) {
VMul(A, Len, LenInv[1]);
return;
}
U32 Ws[MaxExp];
Ws[0] = WbInv[Exp];
for (int i = 1; i < Exp; ++i)
Ws[i] = MMul(Ws[i - 1], Ws[i - 1]);
NttInv2(A, Len, Ws[Exp - 2]);
if (Exp == 2) {
VMul(A, Len, LenInv[2]);
return;
}
NttInv3(A, Len, Ws[Exp - 3]);
if (Exp == 3) {
VMul(A, Len, LenInv[3]);
return;
}
for (int i = 3; i < Exp; ++i) {
U32 ChkSiz = 1u << i;
U32 Wn = Ws[Exp - 1 - i];
U32 tw2 = MMul(Wn, Wn);
U32 tw3 = MMul(tw2, Wn);
U32 tw4 = MMul(tw3, Wn);
U32 tw5 = MMul(tw4, Wn);
U32 tw6 = MMul(tw5, Wn);
U32 tw7 = MMul(tw6, Wn);
U32 twn = MMul(tw7, Wn);
__m256i vw32 = _mm256_set_epi32(tw7, tw6, tw5, tw4, tw3, tw2, Wn, 1);
__m256i vwn = _mm256_set1_epi64x(twn);
for (U32 j = 0; j < Len; j += 2u << i) {
U32* A_ = A + j;
U32* B_ = A_ + ChkSiz;
__m256i vw = vw32;
for (U32 k = 0; k < ChkSiz; k += 8) {
__m256i vw0 = VEx0(vw);
__m256i vw1 = VEx1(vw);
__m256i vb = VMul(VLod(B_ + k), vw0, vw1);
vw = VMul(vw0, vw1, vwn, vwn);
__m256i va = VLod(A_ + k);
__m256i vc = VAdd(va, vb);
__m256i vd = VSub(va, vb);
VSto(A_ + k, vc);
VSto(B_ + k, vd);
}
}
}
VMul(A, Len, LenInv[Exp]);
}
inline int Log2Ceil(U32 N) {
static const U8 Table[32] = {
0, 9, 1, 10, 13, 21, 2, 29,
11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7,
19, 27, 23, 6, 26, 5, 4, 31,
};
N = (N << 1) - 1;
N |= N >> 1;
N |= N >> 2;
N |= N >> 4;
N |= N >> 8;
N |= N >> 16;
return (int) Table[(N * 0x07c4acddu) >> 27];
}
}
const int N=262144+10;const int M=7*1e6+10;typedef unsigned int uit;typedef unsigned long long ll;
const ll mod=998244353;const ll GU=mod/2;
template <typename T>inline void gm(T*& bas,int siz,T*& op){op=bas;bas+=siz;}
inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a%mod)if(p&1)r=r*a%mod;return r;}
int rv[22][N];ll rt[2][22];int ulg[N];uit tr1[N];uit tr2[N];uit B_bas[M];uit* B_t;
int zhi[N];int ct;bool book[N];int phi[N];int mi[N];int uni[N];
uit pre[N];uit suf[N];char mde[N][6];int siz[N];
inline void iter(uit* a,uit* b,int l1,int l2,int rt1,int rt2)
{
int d=ulg[(l1-1)*rt1+1];
for(int i=0;i<(1<<d);i++)tr1[i]=0;for(int i=0;i<(1<<d);i++)tr2[i]=0;
for(int i=0;i<l1;i++)tr1[i*rt1]=a[i];for(int i=0;i<l1;i++)tr2[i*rt2]=a[i];
NTT::NttFwd(tr1,d);NTT::NttFwd(tr2,d);
pre[0]=tr2[0];for(int i=1;i<(1<<d);i++)pre[i]=(ll)pre[i-1]*tr2[i]%mod;
suf[(1<<d)-1]=tr2[(1<<d)-1];for(int i=(1<<d)-2;i>=0;i--)suf[i]=(ll)suf[i+1]*tr2[i]%mod;
for(int i=1;i<(1<<d)-1;i++)tr1[i]=(ll)tr1[i]*pre[i-1]%mod*suf[i+1]%mod;
tr1[0]=(ll)tr1[0]*suf[1]%mod;tr1[(1<<d)-1]=(ll)tr1[(1<<d)-1]*pre[(1<<d)-2]%mod;ll iv=po(suf[0],mod-2);
for(int i=0;i<(1<<d);i++)tr1[i]=(ll)tr1[i]*iv%mod;
NTT::NttInv(tr1,d);for(int i=0;i<l2;i++)b[i]=tr1[i];
}
struct poly
{
uit* xs;int dg;
inline uit& operator [](const int& x){return xs[x];}
friend bool operator <(poly& a,poly& b)
{
if(a.dg!=b.dg)return a.dg<b.dg;
for(int i=a.dg-1;i>=0;i--)
if(a[i]!=b[i])
{
int key1=(a[i]>GU)?(int)a[i]-(int)mod:a[i];
int key2=(b[i]>GU)?(int)b[i]-(int)mod:b[i];return key1<key2;
}return false;
}inline void sprit(int z){for(int i=0;i<siz[z];i++)putchar(mde[z][i]);}
inline void prinum(int z){for(int i=1;i<siz[z];i++)putchar(mde[z][i]);}
inline void prit()
{
putchar('(');int i=dg-1;putchar('x');if(i!=1)sprit(i);i--;
while(i>0)
{
if(xs[i]==0){i--;continue;}
int key=(xs[i]>GU)?(int)xs[i]-(int)mod:xs[i];
putchar((key<0)?'-':'+');prinum((key<0)?-key:key);putchar('x');
if(i!=1)sprit(i);i--;
}putchar((xs[i]==mod-1)?'-':'+');putchar('1');putchar(')');
}
}ans[N];int op[N];int hd;vector <int> fj[N];int n;
inline bool cmp(int x,int y){return ans[x]<ans[y];}
inline void solve(int z)
{
scanf("%d",&n);op[++hd]=1;
for(vector <int> :: iterator it=fj[n].begin();it!=fj[n].end();++it)
{
int nw=*it;op[++hd]=nw;if(ans[nw].dg)continue;
gm(B_t,ans[nw].dg=phi[nw]+1,ans[nw].xs);
if(book[nw]==false){for(int i=0;i<=phi[nw];i++)ans[nw][i]=1;continue;}
int rt=nw/uni[nw];int tmp=nw/mi[nw];
if(rt!=1){int p=uni[nw];for(int i=0;i<=phi[p];i++)ans[nw][i*rt]=ans[p][i];}
else iter(ans[tmp].xs,ans[nw].xs,ans[tmp].dg,ans[nw].dg,mi[nw],1);
}sort(op+1,op+hd+1,cmp);
for(int i=1;i<=hd;i++)ans[op[i]].prit();putchar('\n');
}inline void clear(){hd=0;}
int main()
{
uni[1]=mi[1]=phi[1]=1;for(int i=2;i<=(int)1e5;i++)
{
if(book[i]==false){zhi[++ct]=i;phi[i]=i-1;uni[i]=mi[i]=i;}
for(int j=1;j<=ct&&i*zhi[j]<=(int)1e5;j++)
{
int t=i*zhi[j];book[t]=true;mi[t]=zhi[j];
if(i%zhi[j]==0){uni[t]=uni[i];phi[t]=phi[i]*zhi[j];break;}
else uni[t]=uni[i]*zhi[j],phi[t]=phi[i]*(zhi[j]-1);
}
}for(int d=1,i=1;i<N;i++)d=(((1<<d)<i)?d+1:d),ulg[i]=d;
for(int i=2;i<=(int)1e5;i++)
for(int j=i;j<=(int)1e5;j+=i)fj[j].push_back(i);NTT::NttInitAll(20);
for(int i=2;i<=(int)1e5;i++)
{
int hd=0;for(int p=i;p;p/=10)mde[i][hd++]='0'+p%10;mde[i][hd++]='^';
reverse(mde[i],mde[i]+hd);siz[i]=hd;
}B_t=B_bas;gm(B_t,ans[1].dg=2,ans[1].xs);ans[1][1]=1;ans[1][0]=mod-1;
int T;scanf("%d",&T);for(int z=1;z<=T;z++)solve(z),clear();return 0;
}
```
好了让我们来看正解是什么，事实上正解仅仅基于一个简单的事实
$$\sum_{d|n}2^{\omega(d)}\phi(d)$$
并不大,所以我们暴力计算这个式子就行了
$$\Phi(d,x)=\prod_{t|d}
(x^{d/t}-1)^{\mu(t)}$$
也就是说我们一个一个的把$(x^{d/t}-1)$这些式子乘或者除到我们的多项式上就可以了，巧妙的控制一下循环顺序乘或者除一次的复杂度就是$O(\phi(d))$的
~~是不是令人吐血~~
这里是简单的多的ac代码，而且还比ntt做法块4倍~
上代码~
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=262144+10;const int M=7*1e6+10;
template <typename T>inline void gm(T*& bas,int siz,T*& op){op=bas;bas+=siz;}
int B_bas[M];int* B_t;int zhi[N];int ct;bool book[N];int phi[N];
int uni[N];char mde[N][10];int siz[N];int mu[N];
struct poly
{
int* xs;int dg;
inline int& operator [](const int& x){return xs[x];}
friend bool operator <(poly& a,poly& b)
{
if(a.dg!=b.dg)return a.dg<b.dg;
for(int i=a.dg-1;i>=0;i--)if(a[i]!=b[i])return a[i]<b[i];return false;
}inline void sprit(int z){for(int i=0;i<siz[z];i++)putchar(mde[z][i]);}
inline void prinum(int z){for(int i=1;i<siz[z];i++)putchar(mde[z][i]);}
inline void prit()
{
putchar('(');int i=dg-1;putchar('x');if(i!=1)sprit(i);i--;
while(i>0)
{
if(xs[i]==0){i--;continue;}
putchar((xs[i]<0)?'-':'+');
prinum(xs[i]<0?-xs[i]:xs[i]);putchar('x');
if(i!=1)sprit(i);i--;
}putchar((xs[i]==-1)?'-':'+');putchar('1');putchar(')');
}
inline void mult(int p){for(int i=dg-1;i>=0;i--)xs[i]=-xs[i],xs[i]+=(i>=p)?xs[i-p]:0;}
inline void dive(int p){for(int i=0;i<dg;i++)xs[i]=-xs[i],xs[i]+=(i>=p)?xs[i-p]:0;}
}ans[N];int op[N];int hd;vector <int> fj[N];int n;
inline bool cmp(int x,int y){return ans[x]<ans[y];}
inline void solve()
{
scanf("%d",&n);
for(vector <int> :: iterator it=fj[n].begin();it!=fj[n].end();++it)
{
int nw=*it;op[++hd]=nw;if(ans[nw].dg)continue;
gm(B_t,ans[nw].dg=phi[nw]+1,ans[nw].xs);
if(book[nw]==false){for(int i=0;i<=phi[nw];i++)ans[nw][i]=1;continue;}
int rt=nw/uni[nw];
if(rt!=1){int p=uni[nw];for(int i=0;i<=phi[p];i++)ans[nw][i*rt]=ans[p][i];}
else
{
ans[nw][0]=1;
for(vector <int>:: iterator it=fj[nw].begin();it!=fj[nw].end();++it)
if(mu[*it]==1)ans[nw].mult(nw/(*it));else if(mu[*it]==-1)ans[nw].dive(nw/(*it));
}
}sort(op+1,op+hd+1,cmp);
for(int i=1;i<=hd;i++)ans[op[i]].prit();putchar('\n');
}inline void clear(){hd=0;}
int main()
{
mu[1]=uni[1]=phi[1]=1;for(int i=2;i<=(int)1e5;i++)
{
if(book[i]==false){zhi[++ct]=i;phi[i]=i-1;uni[i]=i;mu[i]=-1;}
for(int j=1;j<=ct&&i*zhi[j]<=(int)1e5;j++)
{
int t=i*zhi[j];book[t]=true;
if(i%zhi[j]==0){uni[t]=uni[i];phi[t]=phi[i]*zhi[j];mu[t]=0;break;}
else uni[t]=uni[i]*zhi[j],phi[t]=phi[i]*(zhi[j]-1),mu[t]=-mu[i];
}
}for(int i=1;i<=(int)1e5;i++)
for(int j=i;j<=(int)1e5;j+=i)fj[j].push_back(i);
for(int i=2;i<=(int)1e5;i++)
{
int hd=0;for(int p=i;p;p/=10)mde[i][hd++]='0'+p%10;mde[i][hd++]='^';
reverse(mde[i],mde[i]+hd);siz[i]=hd;
}B_t=B_bas;gm(B_t,ans[1].dg=2,ans[1].xs);ans[1][1]=1;ans[1][0]=-1;
int T;scanf("%d",&T);for(int z=1;z<=T;z++)solve(),clear();return 0;
}
```