旧试题
larsr
·
·
题解
两年前 @command_block 使用多元积性函数做到了 O(n^{5/4}+n\log^3n)，原文，今天回来补了一下。他没有申请题解，就当这是给原文的一个索引？
这里讲一下前面的 O(n\sqrt n) 做法。
设置三元函数 f(x,y,z)=d(xyz)，考虑拟合该函数 g(x,y,z)=d(x)d(y)d(z)。求得 h=\frac{f}{g}，因为 f,g 是积性的，那么 h 也是积性的。
\begin{align*}
\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^Cf(i,j,k)&=\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\sum_{x|i}\sum_{y|j}\sum_{z|k}h(x,y,z)g(\frac{i}{x}, \frac{j}{y}, \frac{k}{z})\\
&=\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\sum_{x|i}\sum_{y|j}\sum_{z|k}h(x,y,z)d(\frac{i}{x})d(\frac{j}{y})d(\frac{k}{z})\\
&=\sum_{x=1}^A\sum_{y=1}^B\sum_{z=1}^Ch(x,y,z)S_d(\frac{i}{x})S_d(\frac{j}{y})S_d(\frac{k}{z})
\end{align*}
通过推导发现在质数 p 下有值的位置只有 h(1,1,1)=1,h(p,p,1)=h(p,1,p)=h(1,p,p)=-1,h(p,p,p)=2，经过原文的证明发现 h 有值的位置是 O(n\sqrt n) 级别的，那么复杂度也是 O(n\sqrt n)。
代码比三元环好写很多。