ACM – 莫比乌斯反演

点击量:20

昨天卡了这道题目,今天特意来看看莫比乌斯反演。

title

其中,$∑_{d|n}$含义为整除.


ACdreamer大大的讲解


看了这篇文章即可= =

wikipedia的公式:

title

title

以上就是具体的公式,此外,还有线性筛法:

void Init()
{
    memset(vis,0,sizeof(vis));
    mu[1] = 1;
    cnt = 0;
    for(int i=2; i<N; i++)
    {
        if(!vis[i])
        {
            prime[cnt++] = i;
            mu[i] = -1;
        }
        for(int j=0; j<cnt&&i*prime[j]<N; j++)
        {
            vis[i*prime[j]] = 1;
            if(i%prime[j]) mu[i*prime[j]] = -mu[i];
            else
            {
                mu[i*prime[j]] = 0;
                break;
            }
        }
    }
}

这段代码也是摘自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)$的

就是这样。

发表评论

电子邮件地址不会被公开。 必填项已用*标注