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

首先，

.

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

，为了让后面的式子更简洁，这里从0开始求和。

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

考虑拉格朗日插值公式

其中是所求函数图象上的个点。我们需要个点，不妨取时的前缀和，记为，要插的函数

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

我的代码