Tag: 莫比乌斯反演

2 篇文章

BZOJ3994 [SDOI2015]约数个数和
题面 设$f(x)$为x的约数个数,给定$N$、$M$,求$\sum_{i=1}^{n} \sum_{j=1}^{m} f(i j)$ 思路 推导过程 有个定理$f(ij)=\sum_{x | i} \sum_{y | j}[g c d(x, y)=1]$。你问我如何推导,我只能告诉你无可奉告——这里纸太小,写不下。 然后大力推导以后数论分块即可,…
莫比乌斯反演&杜教筛学习小结
本文参考借鉴于知乎上$Syu Gau$与$阮行止$在$如何证明莫比乌斯反演?$这一问题下的回答. 前置知识 1.卷积 首先我们先设$f,g$为两个数论函数。 则卷积定义为$(f\times g)(n)=\sum_{ij=n}f(i)g(j)$。(注意本文的$\times$不是乘,是卷积运算,乘都已省略) 易证卷积满足交换律与结合律。 那么让我们设想…