莫比乌斯反演

余数求和

对于任意整数 \(x\in[1,n]\) 设 \(g(x)=\lfloor\frac{k}{\lfloor\frac{k}{x}\rfloor}\rfloor\)

\(\because f(x)=k/x\) 单调递减

又 \(g(x)=\lfloor\frac{k}{\lfloor\frac{k}{x}\rfloor}\rfloor\geq\lfloor\frac{k}{(\frac{k}{x})}\rfloor=x\)

\(\therefore \lfloor\frac{k}{g(x)}\rfloor\leq\lfloor\frac{k}{x}\rfloor\)

\(\because \lfloor\frac{k}{g(x)}\rfloor\geq\lfloor\frac{k}{(\frac{k}{\lfloor\frac{k}{x}\rfloor})}\rfloor=\lfloor\frac{k}{k}\lfloor\frac{k}{x}\rfloor\rfloor=\lfloor\frac{k}{x}\rfloor\)

\(\therefore \lfloor\frac{k}{g(x)}\rfloor=\lfloor\frac{k}{x}\rfloor\)

综上得，对于 \(i\in[x,\lfloor\frac{k}{\lfloor\frac{k}{x}\rfloor}\rfloor]\),\(\lfloor\frac{k}{i}\rfloor\)的值相等

莫比乌斯函数

\(\mu(n) = \begin{cases} 0, & \exists i \in [1,m],c_i>1 \\ 1, & m \equiv 0 \pmod 2,\forall i \in [1,m],c_i=1 \\ -1, & m \equiv 1 \pmod 2,\forall i \in [1,m],c_i=1 \end{cases}\)

线性筛法

Code:

    mu[1]=1;
    for(re int i=2;i<N;i++){
        if(!mark[i]){
            p[++cnt]=i;
            mu[i]=-1;
        }
        for(re int j=1;j<=cnt&&i*p[j]<N;j++){
            mark[i*p[j]]=1;
            if(!(i%p[j])){
                mu[i*p[j]]=0;
                break;
            }else mu[i*p[j]]=-mu[i];
        }
    }

莫比乌斯反演

狄利克雷卷积

对于 \(h(n)=\sum_{d|n} f(d)*g(\frac{n}{d})\)

记作 \(h=f\otimes g\) ,若 \(f,g\) 为积性函数,则 \(h\) 也为积性函数

对于给定数论函数 \(f,g\)

\(f(n)=\sum_{d|n} g(d) \iff g(n)=\sum_{d|n} \mu(d)*f(\frac{n}{d})\)

性质：

1. \(\sum_{d|n} \mu(d) = [n=1]\)

2. \(\sum_{d|n} \phi(d) =n\)

杜教筛

莫比乌斯反演

原文：https://www.cnblogs.com/wwlwQWQ/p/11272819.html