题解 | #莫比乌斯反演与傅里叶变换#

首先，

$\sum_{i=1}^{n}\sum_{j|i}f(j) = \sum_{j=1}^{n}f(j)\sum_{i=1}^{n}[j|i] = \sum_{j=1}^{n}f(j)\cdot \lfloor \frac{n}{j}\rfloor$ .

所以考虑数论分块，试图在允许的时间内求 $f(j)$ 的前缀和，即求

$\sum_{j=0}^{i}f(j)$ ，为了让后面的式子更简洁，这里从0开始求和。

因为 $f$ 是一个 $m-1$ 次多项式，所以 $f$ 的前缀和是一个 $m$ 次多项式，我们可以使用拉格朗日插值，先求 $m+1$ 个位置的前缀和，然后插出任意位置的前缀和。

考虑拉格朗日插值公式

$f(x)=\sum_{i=1}^{n}\prod_{j=1,j\ne i}^{n}\frac{x-x_j}{x_i-x_j}y_i$

其中 $x_i, y_i$ 是所求函数图象上的 $n$ 个点。我们需要 $m+1$ 个点，不妨取 $i=0,\dots, m$ 时的前缀和，记为 $pre[0], \dots, pre[m]$ ，要插的函数

$pre(x)=\sum_{i=0}^{m}\prod_{j=0, j\ne i}^{m}\frac{x-j}{i-j}pre[i]$

被求和的每一项系数的分子和分母都是一些连续整数的乘积，可以用两个数的阶乘相除快速求得，而阶乘和阶乘的逆元可以预处理。