MOCK PTS 20231127 B 数论题技巧拾贝

超大整数因数的映射方式

若有 $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)$。