zcmimi's blog

arrow_back卷积共2篇文章

avatar
zcmimi
2020-03-15 17:10:00

前置知识: 狄利克雷卷积

求积性函数f的前缀和:

S(n)=\sum_{i=1}^nf(i)

大部分题目都是可以线性筛的,可是某些丧心病狂的出题人会: n\le 10^{12}!

这时候需要用杜教筛了

我们构造另

avatar
zcmimi
2020-03-14 22:46:00

数论函数

  1. 加法

    逐项相加

    (f+g)(x)=f(x)+g(x)

  2. 数乘

    (xf)(n)=x\cdot f(n)

定义

两个数论函数的狄利克雷卷积∗

t=f*g等价于

$$t(n)=\sum_{i|n}f(i)

1/1
Search
search