前置知识
杜教筛
概念
杜教筛用于解决数论函数 (f(n)) 的前缀和问题, 即求 :
[S(n)=sum_{i=1}^{n}f(i)
]
结论
对于任意数论函数 (g(n)) , 都有
[sum_{i=1}^{n}sum_{d|i}f(d)gleft(frac{i}{d}
ight)=sum_{i=1}^{n}g(i)Sleft(leftlfloorfrac{n}{i}
ight
floor
ight)
]
即
[sum_{i=1}^{n}(f*g)(i)=sum_{i=1}^{n}g(i)Sleft(leftlfloorfrac{n}{i}
ight
floor
ight)
]
(PS.) ((f*g)) 表示函数 (f(n)) 与 (g(n)) 的 (Dirichlet) 卷积.
证明 :
[egin{align}
sum_{i=1}^{n}sum_{d|i}f(d)gleft(frac{i}{d}
ight)
&= sum_{i=1}^{n}g(i)sum_{j=1}^{lfloorfrac{n}{i}
floor}f(j) \
&= sum_{i=1}^{n}g(i)Sleft(leftlfloorfrac{n}{i}
ight
floor
ight)
end{align}
]
得证.
用法
[egin{align}
&ecause
sum_{i=1}^{n}(f*g)(i)=sum_{i=1}^{n}g(i)Sleft(leftlfloorfrac{n}{i}
ight
floor
ight)
=g(1)S(n)+sum_{i=2}^{n}g(i)Sleft(leftlfloorfrac{n}{i}
ight
floor
ight). \
& herefore
g(1)S(n)=sum_{i=1}^{n}(f*g)(i)-sum_{i=2}^{n}g(i)Sleft(leftlfloorfrac{n}{i}
ight
floor
ight).
end{align}
]
后面那段可以用数论分块解决, 如果能快速求得 (sum_{i=1}^{n}(f*g)(i)) , 即函数 ((f*g)(n)) 的前缀和, 那么我们就可以不断递归地求出 (S(n)) , 并用 (map) 存下已经求得的值
在实际题目中, 我们会根据 (f(n)) 来确定 (g(n)) , 以快速地求出 ((f*g)(n)) 的前缀和. (g(n)) 的选取可以参照下表.
[egin{align}
varepsilon &= mu *1 \
ID &= varphi * 1 \
varphi &= mu * ID
end{align}
]
关于这些函数的意义详见 Dirichlet卷积 莫比乌斯函数 莫比乌斯反演 学习笔记