快速回忆莫比乌斯反演

· · 个人记录

0.数论分块

代码

for(int l=1,r;l<=n;l=r+1)
{
    r=n/(n/l);
    ans+=(r-l+1)*fuction(n/l);
    //左边为序列长度，右边为相同的贡献
}

1.莫比乌斯函数

定义

μ(n)=​ \begin{cases} 1&n=1\\ 0&n含有平方因子\\ (-1)^k& k为n的本质不同质因子个数 \end{cases}​

性质

\sum_{d|n}μ(d)= \begin{cases} 1&n=1\\ 0&n≠1 \end{cases}

结论

[\gcd(i,j)=1]=\sum_{d|\gcd(i,j)}μ(d)

代码

线性筛莫比乌斯函数

void pre()
{
    mu[1]=1;
    for(int i=2;i<=10000000;i++)
    {
        if(!v[i]) v[i]=p[++cnt]=i,mu[i]=-1;
        to=10000000/i;
        for(int j=1;j<=cnt&&p[j]<=to&&p[j]<=v[i];j++)
        {
            v[p[j]*i]=p[j];
            if(p[j]==v[i]) mu[p[j]*i]=0;
            else mu[p[j]*i]=-mu[i];
        }
    }
}

2.欧拉函数

定义

φ(n)=​\sum_{i=1}^n[\gcd(n,i)=1]

性质

\sum_{d|n}φ(d)=n

结论

\gcd(i,j)=\sum_{d|\gcd(i,j)}φ(d)

代码

void pre()
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!v[i]) v[i]=p[++m]=i,phi[i]=i-1;
        to=n/i;
        for(int j=1;j<=m&&p[j]<=to&&p[j]<=v[i];j++)
        {
            v[p[j]*i]=p[j];
            if(p[j]==v[i]) phi[p[j]*i]=p[j]*phi[i];
            else phi[p[j]*i]=phi[p[j]]*phi[i];
        }
    }
}

3.莫比乌斯变换

形式一

f(n)=\sum_{d|n}g(d)\\ g(n)=\sum_{d|n}μ(d)f(\frac{n}{d})

形式二

f(n)=\sum_{n|d}g(d)\\ g(n)=\sum_{n|d}μ(\frac{d}{n})f(d)

可以将形式二转化成形式一进行变换

4.经典操作

带权互质数对贡献和

用莫比乌斯函数进行变换

\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=1]ij\\ \sum_{i=1}^n\sum_{j=1}^n\sum_{x|\gcd(i,j)}μ(x)ij\\ \sum_{i=1}^n\sum_{j=1}^n\sum_{x|i}\sum_{x|j}μ(x)ij\\ \sum_{x=1}^n\sum_{i=1}^n\sum_{j=1}^n[x|i][x|j]μ(x)ij\\ \sum_{x=1}^nμ(x)\sum_{i=1}^n\sum_{j=1}^n[x|i][x|j]ij\\ \sum_{x=1}^nμ(x)\sum_{i=1}^{⌊\frac{n}{x}⌋}\sum_{j=1}^{⌊\frac{n}{x}⌋}xi⋅xj\\ \sum_{x=1}^nμ(x)x^2\sum_{i=1}^{⌊\frac{n}{x}⌋}\sum_{j=1}^{⌊\frac{n}{x}⌋}ij\\ \sum_{x=1}^nμ(x)x^2\sum_{i=1}^{⌊\frac{n}{x}⌋}i\sum_{j=1}^{⌊\frac{n}{x}⌋}j\\ \sum_{x=1}^nμ(x)x^2\texttt{sum}^2(⌊\frac{n}{x}⌋)\\

然后数论分块就几把完了

带权数对最大公因数贡献和

用欧拉函数进行变换

把上面的莫比乌斯函数改成欧拉函数就行了