记个笔记, 公式存储空间只有1kb的我就不用记这玩意啦!
首先用狄雷克利卷积:
$$ (f\cdot g)(i) = \sum_{d|i} f(d)g(\frac{i}{d}) $$
求前缀和:
$$ \sum_{i=1}^n (f\cdot g)(i) = \sum_{i=1}^n \sum_{d|i} f(d)g(\frac{i}{d}) $$
把右边求和后面的因子d提前, 设S函数为f的前缀和, 那么有
$$ \sum_{i=1}^n (f\cdot g)(i) = \sum_{d=1}^n g(d) S(\lfloor \frac{n}{d} \rfloor) $$
然后把右边d=1的情况提出来, 把d>1的求和移动到左边:
$$ \sum_{i=1}^n (f\cdot g)(i) -\sum_{d=2}^n g(d) S(\lfloor \frac{n}{d} \rfloor)=g(1)S(n)$$
如果要求S(n), 只要能快速求g(1), g和f的卷积就可以搞定啦!
Join the discussion