狄利克雷卷积学习笔记
 蒟蒻尚在学习,请各位dalao不要相信本文的任何一个字,包括标点符号.
 什么是狄利克雷卷积
 狄利克雷卷积定义式如下:
 也可以写作:
 怎么算狄利克雷卷积
 单独计算$f*g(n)$
 显然我们可以根据定义式暴力计算,枚举$i$即可,复杂度$O(\sqrt{n})$
 这里就不上代码了,跟暴力枚举质数长得基本上一模一样.
 计算$f*g$
 如果再像暴力计算那样,复杂度将达到恐怖的$O(n\sqrt{n})$.
 但是我们可以从质数筛(埃塞)的想法入手,我们可以直接枚举一个$i$,再为它的倍数上的值加上对应的贡献就好.时间复杂度$O(nlogn)$.
 代码大概长这样w
 怎么样,是不是比FFT容易一千万倍?