超大整数因数的映射方式
若有 $n=\prod_{i=1}^k p_i^{c_i}$，则其所有 $m=\prod_{i=1}^k(c_i+1)$ 个因数可以被方便地映射到 $[0,m)$ 中整数上。具体地，我们设
$$
\newcommand\fcs{\operatorname{fcs}}
\newcommand\fcp{\operatorname{fcp}}
\begin{aligned}
\fcs(i)&=\prod_{j=i}^{k}(c_j+1)\\
\fcp(i)&=\prod_{j=1}^i(c_j+1)
\end{aligned}
$$
规定 $\fcs(k+1)=\fcp(0)=1$。则若有 $x=\prod_{i=1}^kp_i^{e_i},0\leq e_i\leq c_i$，它将被映射为 $f(x)=\sum_{i=1}^k\fcs(i+1)e_i$。
这种映射方式好处多多：我们得以在 $\newcommand\bigO{\operatorname{O}}\bigO(k)$ 的时间内计算任意指数序列的映射，或将一个映射唯一还原为指数序列（对 $\fcs(i+1)$ 逐层取模即可）；更有 $m-1-f(x)=f(n/x)$，在本题里极大地方便了计算。它还方便我们在 $\bigO(m{\color{blue}\ \log m})$（${\color{blue}k\leq \log_2 m}$）的时间内求高维前缀和——或者用数论的行话，狄利克雷前缀和：依序枚举 $p_i$，枚举 $e_i,0<e_i\leq c_i$，再枚举前后缀两维度分拆出的映射数 $x,y$，利用 $\fcp(i-1)$ 和 $\fcs(i+1)$ 可以轻松拼合出所需映射。
单位根反演与莫比乌斯函数
记 $\newcommand\w{\omega}\w_n=\exp(2\pi/n)$。有整数 $t$，则 $\sum_{i=0}^{n-1}\w_n^{it}=n[n\mid t]$。
由等比数列求和公式可以轻松证明。精妙的是下面一条：
$$
\sum_{\substack{0\leq p<n\\p\perp n}}\w_n^p=\mu(n)
$$
对于 $\gcd(p,n)$ 的条件，我们注意到 $\sum_{d\mid n}\mu(d)=[n=1]$ 常被用来处理互质条件，遂尝试利用之：
$$
\begin{aligned}
&\sum_{\substack{0\leq p<n\\p\perp n}}\w_n^p\\
=&\sum_{d\mid n}\mu(d)\sum_{t=1}^{n/d}\w_n^{d\cdot t}\\
=&\sum_{d\mid n}\mu(d)\sum_{t=1}^{n/d}\w_{n/d}^t\\
=&\sum_{d\mid n}\mu(d)\left[\frac{n}{d}\mid 1\right]\\
=&\mu(n).
\end{aligned}
$$
同样地，如果我们在指数上添加额外因子 $q$，也即 $\sum_{\substack{0\leq p<n\\p\perp n}}\w_n^{pq}$，也可以导出类似结论：它等于
$$
\sum_{d\mid \gcd(n,q)}\mu(\frac{n}{d})d.
$$
模 $z^n$ 意义下 $F(z)$ 的循环卷积
求出 $F(\w_n^t),t=0,1,\cdots,n-1$。则 $(F(\w_n^t))^k$ 就等于 $F(z)$ 在 ${}\bmod n$ 意义下的 $k$ 次幂求 $z=\w_n^k$ 点值的结果。这可以由单位根的性质说明。
莫比乌斯函数与其他任意函数的狄利克雷卷积
也就是对于 $n$，对其所有因数 $x$，求
$$
\sum_{d\mid x}f(d)\mu\left(\frac{x}{d}\right)
$$
设 $n$ 有 $m$ 个因数。这可以在 $\bigO(m\log m)$ 的时间内求出。注意到 $\mu(x)\in\{0,-1,1\}$，这也就意味着对任意质因子 $p_i$，设 $d$ 有 $e_i$ 个、$x$ 有 $c_i$ 个，则只有 $c_i-e_i\leq 1$ 时 $f(d)$ 才可能被计入最终答案。我们可以仿照狄利克雷前缀和，在前 $i$ 个阶段处理完“与 $x$ 在 $p_1,p_2,\cdots,p_i$ 的指数上差距 $\leq 1$（$c_j-e_j\leq 1$），而在 $p_{i+1},\cdots$ 的指数上与 $x$ 完全相同（$c_j=e_j$）”的所有 $d$ 的贡献。记它是 $h(x,i)$；初始有 $h(x,0)=f(x)$，转移有 $h(x,i+1)=h(x,i)+(-1)h(x/p^{i+1},i)$。
近期评论