ACM – 莫比乌斯反演
昨天卡了这道题目，今天特意来看看莫比乌斯反演。
其中，$∑_{d|n}$含义为整除.
看了这篇文章即可= =
wikipedia的公式:
以上就是具体的公式，此外，还有线性筛法:
这段代码也是摘自AC大大。我们得到这个东西有什么用？
简单来说，就是简化计算数论函数和的计算的过程，进行加速。
在HDU5212中，给出的题解是：
这道题需要一些莫比乌斯反演、线性筛的知识
定义$f(x)=x∗(x−1)$
题目所求即为$\Sigma(f(gcd(ai,aj)|i!=j,1≤i,j≤n)$
先用线性筛求出miu在[1,10000]的函数值
利用莫比乌斯反演公式我们可以$O(vlogv)$暴力求解出函数g（就是$f(n)/miu$）在[1,10000]的函数值，其中g满足：
$\Sigma(g(d)|x)$
这样所求答案即为：
$\Sigma(g(d)∗cnt(d)∗cnt(d)|1≤d≤10000)$，其中cnt函数满足：
cnt(x)=在a1,a2,..,an中是x的倍数的个数
而cnt的取值也可以$O(vlogv)$暴力计算出
所以总的时间复杂度就是$O(vlogv)$的
就是这样。