这东西分明就是玄学暴力
用来求简单的数论函数的前缀和,像φ,μ这类的东西
当然约数和,约数个数之类的也是可以的
数论函数是指定义域是整数陪域是复数的函数
定义两个数论函数f,g
它们的狄利克雷纪念方式有哪些雷卷积表示f?g,设卷起来得到的新函数是h
显然它满足交换结合律,对加法满足分配律
显然有以下常见的卷积形式
任意函数卷积单位え仍为它本身
要使g和g?μ尽量容易求可以想到g用1函数是比较合适的,即g(i)=1
可以用线筛预处理前(√n)或者n23的S后面减的部分分块处理,遞归下去再哈希或者什么东西把算过的S记忆化一下
复杂度取决于预处理的多少
实验和理论都证明,预处理前n23个S总复杂度最优,为O(n23)
据说證明要用积分然而我并不会。。
对于求欧拉函数的前缀和方法也是一样的,g仍取1只不过g?φ=id