莫比乌斯反演

标签：lfloor frac ast 乌斯 sum rfloor mu 反演莫比

前置芝士：数论分块

求 \(\sum\limits_{i=1}^n\lfloor\frac{n}{i}\rfloor\)，其中 \(n\le10^{12}\)。

可以发现，\(\lfloor\frac{n}{i}\rfloor\) 最多只有 \(\sqrt{n}\) 种取值，所以只需要枚举每种取值对应 \(i\) 的取值范围即可。

ll ans = 0;
for(int i = 1,j;i <= n;i = j+1)
{
    j = n/(n/i);
    ans += (n/i)*(j-i+1);
}

积性函数：

如果函数 \(f\) 满足 \(\forall a,b,\gcd(a,b)=1,f(ab)=f(a)f(b)\)，则 \(f\) 为积性函数。

欧拉函数：\(\varphi(n)\)，即 \(1\) 到 \(n\) 中与 \(n\) 互质的个数。
莫比乌斯函数：\(\mu(i)=\begin{cases}1&n=1\\(-1)^k&n=p_1p_2\ldots p_k\\ 0&otherwise\end{cases}\)
因子函数：\(d(n)\)，即 \(n\) 的因子个数。
除数函数：\(\sigma(n)=\sum\limits_{d\mid n}d\)，即 \(x\) 的因子之和。

完全积性函数：

如果函数 \(f(n)\) 满足 \(\forall a,b,f(ab)=f(a)f(b)\)，则 \(f(n)\) 为完全积性函数。

常数函数：\(I(n)=1\)
恒等函数：\(Id(n)=n\)
单位函数：\(\varepsilon(n)=[n=1]\)

狄利克雷卷积：

\((f\ast g)(n)=\sum\limits_{d\mid n}f(d)g(\frac{n}{d})\)

性质：

交换律：\(f\ast g=g\ast f\)
结合律：\((f\ast g)\ast h=f\ast(g\ast h)\)
分配律：\((f+g)\ast h=f\ast h+f\ast h\)
如果 \(f,g\) 是积性函数，则 \(f*g\) 也是积性函数。比如：
- \(Id\ast I=\sigma\)
- \(I\ast I=d\)
- \(\varphi\ast I=Id\)
- \(\mu\ast I=\varepsilon\)
下面是根据上面推出来的：
- \(\varepsilon\ast f=f\)，即 \(\varepsilon\) 与任何函数进行狄利克雷卷积后都是函数本身；
- \(\varphi\ast d=\varphi\ast I\ast I=Id\ast I=\sigma\)
- \(\because\varepsilon\ast Id=Id \therefore\mu\ast I\ast Id=\varphi\ast I \therefore\mu\ast Id=\varphi\)
- \(\mu\ast \sigma=\mu\ast Id\ast I=\varepsilon\ast Id=Id\)

莫比乌斯反演：\([n=1]=\sum\limits_{d\mid n}\mu(d)\)

其实莫比乌斯反演还有一种形式：\(g(n)=\sum\limits_{d\mid n}f(d)\leftrightarrow f(n)=\sum\limits_{d\mid n}\mu(d)d(\frac{n}{d})\)，也可以写成：\(f\ast I=g\leftrightarrow f=g\ast\mu\)。

证明：\(\mu\ast I=\varepsilon\)

当 \(n=1\) 时显然成立，当 \(n>1\) 时，设 \(n=p_1^{c_1}p_2^{c_2}\ldots p_k^{c_k}\)，由于有平方因子的数的 \(\mu\) 为 \(0\)，所以只需要证 \(n=p_1p_2\ldots p_k\) 时 \(\sum\limits_{d\mid n}\mu(\frac{n}{d})=0\)成立即可。

\[\begin{align} \mu\ast I &= \sum_{d\mid n}\mu(\frac{n}{d}) \\ &=\mu(1)+\mu(p_1)+\ldots +\mu(p_k)+\mu(p_1p_2)+\mu(p_1p_3)+\ldots +\mu(p_{k-1}p_k)+\ldots +\mu(p_1p_2\ldots p_k) \\ &= \sum_{i=0}^k(-1)^i\binom{k}{i} \\ &= 0 \end{align} \]

欧拉反演：\(n=\sum\limits_{d\mid n}\varphi(d)\)

证明：\(\varphi\ast I=Id\)

设 \(n=p_1^{c_1}p_2^{c_2}\ldots p_k^{c_k}\)，因为 \(\varphi\) 是积性函数，则只需要证 \(n'=p^c\) 时成立即可。

\[\begin{align} \varphi\ast 1&=\sum_{d\mid n}\varphi(\frac{n}{d}) \\ &=\sum_{i=0}^c\varphi(p^i) \\ &=1+p^0\times(p-1)+p^1\times(p-1)+\ldots +p^{c-1}\times(p-1) \\ &=p^c \\ &=Id \end{align} \]

线性筛 \(\varphi\) 和 \(\mu\)

线性筛分有重复因子和没重复因子两种情况，直接分情况讨论即可。

int p[N],phi[N],mu[N],cnt;
bool isp[N];
ll sphi[N],smu[N];
void init()
{
    phi[1] = mu[1] = 1;
    for(int i = 2;i < N;i++)
    {
        if(!isp[i]){p[++cnt] = i;phi[i] = i-1;mu[i] = -1;}
        for(int j = 1;j <= cnt&&p[j]*i < N;j++)
        {
            int now = i*p[j];
            vis[now] = 1;
            if(i%p[j]==0)
            {
                phi[now] = phi[i]*p[j];mu[now] = 0;
                break;
            }
            phi[now] = phi[i]*(p[j]-1);mu[now] = -mu[i];
        }
    }
    for(int i = 1;i < N;i++)
        sphi[i] = sphi[i-1]+phi[i],smu[i] = smu[i-1]+mu[i];
}

例题

最基本的应用

求 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=1]\) 和 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^m\gcd(i,j)\)，\(T\) 组数据，\(n,m\le 2\times10^6,T\le 1000\)

题太多了，甚至有十倍经验。

直接莫比乌斯反演（以下默认 \(n\le m\)）：

\[\begin{align} \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1]&=\sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid i,d\mid j}\mu(d) \\ &=\sum_{d=1}^n\mu(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}1 \\ &=\sum_{d=1}^n\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor \end{align} \]

\[\begin{align} \sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)&=\sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid i,d\mid j}\varphi(d) \\ &=\sum_{d=1}^n\varphi(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}1 \\ &=\sum_{d=1}^n\varphi(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor \end{align} \]

发现式子中只有 \(\lfloor\frac{n}{d}\rfloor\) 和 \(\lfloor\frac{m}{d}\rfloor\)，直接数论分块即可，时间复杂度 \(\mathcal{O}(n+T\sqrt{n})\)。

ll ans1 = 0,ans2 = 0;
for(int i = 1,j;i <= n;i = j+1)
{
    j = min(n/(n/i),m/(m/i));
    ans1 += (smu[j]-sum[i-1])*(n/i)*(m/i);
    ans2 += (sphi[j]-sphi[i-1])*(n/i)*(m/i);
}

总结：莫比乌斯反演最重要的就是处理和式，经常推不出式子了就尝试一下交换和式

P2257 YY的GCD

求 \(\sum\limits_{i=1}^n \sum\limits_{j=1}^m[\gcd(i,j)\in prime]\)， \(T\) 组数据，\(n,m\le 10^7,T\le 10^4\)。

考虑枚举 \(\gcd(i,j)\)：

\[\begin{align} \sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)\in prime] &= \sum_{p\in prime}\sum_{i=1}^n \sum_{j=1}^m[\gcd(i,j)=p] \\ &= \sum_{p\in prime}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor} \sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}[\gcd(i,j)=1] \\ &= \sum_{p\in prime}\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor} \mu(d) \lfloor\frac{n}{px}\rfloor \lfloor\frac{m}{px}\rfloor \\ \end{align} \]

枚举 \(T=px\)：

\[=\sum_{T=1}^n \lfloor\frac{n}{T}\rfloor \lfloor\frac{m}{T}\rfloor \sum_{p\mid T,p\in prime}\mu(\lfloor\frac{T}{p}\rfloor) \]

令 \(f(n)=\sum\limits_{p\mid n,p\in prime}\mu(\lfloor\frac{n}{p}\rfloor)\)，只需要预处理出 \(f(n)\) 的前缀和即可。具体的，枚举每一个质数，然后用类似埃式筛的方法求出 \(f(n)\)。时间复杂度 \(\mathcal{O}(n\log\log n+T\sqrt n)\)。

//预处理
for(int i = 1;i <= cnt;i++)
    for(int j = p[i];j < N;j += p[i])
        f[j] += mu[j/p[i]];
for(int i = 1;i < N;i++)f[i] += f[i-1];
//计算
for(int i = 1,j;i <= min(n,m);i = j+1)
{
    j = min(n/(n/i),m/(m/i));
    ans += (f[j]-f[i-1])*(n/i)*(m/i);
}

[P3327 SDOI2015] 约数个数和

设 \(d(n)\) 为 \(n\) 的约数个数，求 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^md(ij)\)，\(T\) 组数据，\(T,n,m\le 5000\)。

考虑转化 \(d(ij)\)，将 \(ij\) 的因子与 \(i\) 和 \(j\) 的因子一一对应。如果 \(ij\) 的因子 \(k\) 中有一个因子 \(p^c\)，\(i\) 中有 \(p^a\)，\(j\) 中有 \(p^b\)，则 \(c\le a+b\)。那么：

如果 \(c\le a\)，那么在 \(i\) 中选择 \(p^a\)；
如果 \(c>a\)，那么在 \(j\) 中选择 \(p^{c-a}\)。

所以如果在 \(i\) 中选择一个因子 \(x\)，在 \(j\) 中选择一个因子 \(y\) 且 \(\gcd(x,y)=1\)，则 \(x,y\) 一定对应一个 \(ij\) 的因子。所以 \(d(ij)=\sum\limits_{x\mid i}\sum\limits_{y\mid j}[\gcd(x,y)=1]\)

\[\begin{align}\sum_{i=1}^n\sum_{j=1}^md(ij)&=\sum_{i=1}^n\sum_{j=1}^m\sum_{x\mid i}\sum_{y\mid j}[\gcd(x,y)=1] \\ &=\sum_{x=1}^n\sum_{y=1}^m\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor[\gcd(x,y)=1] \\ &= \sum_{x=1}^n\sum_{y=1}^m\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\sum_{d\mid x,d\mid y}\mu(i) \\ &=\sum_{d=1}^n\mu(i)\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{x=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{n}{xd}\rfloor\lfloor\frac{m}{yd}\rfloor \\ &= \sum_{d=1}^n\mu(i)(\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{xd}\rfloor)(\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{m}{yd}\rfloor)\end{align} \]

发现括号里面的东西可以预处理，令 \(f(n)=\sum\limits_{i=1}^n\lfloor\frac{n}{i}\rfloor\)，则原式等于 \(\sum\limits_{d=1}^n\mu(i)f(\lfloor\frac{n}{d}\rfloor)f(\lfloor\frac{m}{d}\rfloor)\)，数论分块即可。时间复杂度 \(\mathcal{O}(n\sqrt{n}+T\sqrt{n})\)。

//预处理
for(int i = 1;i < N;i++)
    for(int j = 1,k;j <= i;j = k+1)
    {
        k = i/(i/j);
        f[i] += (k-j+1)*(i/j);
    }
//计算
for(int i = 1,j;i <= min(n,m);i = j+1)
{
    j = min(n/(n/i),m/(m/i));
    ans += (smu[j]-smu[i-1])*f[n/i]*f[m/i];
}

P1829 Crash的数字表格

求：\(\sum\limits_{i=1}^n\sum\limits_{j=1}^m\operatorname{lcm}(i,j)\)，\(T\) 组数据，\(n,m\le 10^7,T\le 10^4\)

因为 \(\operatorname{lcm}(i,j)=\frac{ij}{\gcd(i,j)}=\gcd(i,j)\times\frac{i}{\gcd(i,j)}\times\frac{j}{\gcd(i,j)}\)，枚举 \(\gcd(i,j)\)：

\[\sum_{i=1}^n\sum_{j=1}^m\operatorname{lcm}(i,j)=\sum_{d=1}^nd\times\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)=1]\times ij \]

为了单独计算后半边式子，记：

\[\operatorname{sum}(n,m)=\sum_{d=1}^nd\times\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1]\times ij \]

另外，记 \(S(n)=\sum\limits_{i=1}^ni=\frac{n(n+1)}{2}\)，那么：

\[\begin{align}\operatorname{sum}(n,m)&=\sum_{i=1}^n\sum_{j=1}^mij\times \sum_{d\mid i,d\mid j}\mu(d) \\ &= \sum_{d=1}^n\mu(d)\times d^2\times \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij \\ &=\sum_{d=1}^n\mu(d)d^2\times S(\lfloor\frac{n}{d}\rfloor)S(\lfloor\frac{m}{d}\rfloor)\end{align} \]

其实到这里就可以数论分块套数论分块做了，时间复杂度 \(\mathcal{O}(Tn^{\frac{3}{4}})\)，但事实上原式还可以优化。

\[\sum_{d=1}^nd\times\operatorname{sum}(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)=\sum_{d=1}^nd\times\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)k^2\times S(\lfloor\frac{n}{dk}\rfloor)S(\lfloor\frac{m}{dk}\rfloor) \]

把 \(d\) 乘进去：

\[\sum_{d=1}^n\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)k\times dk\times S(\lfloor\frac{n}{dk}\rfloor)S(\lfloor\frac{m}{dk}\rfloor) \]

先枚举 \(T=dk\)：

\[\sum_{T=1}^nS(\lfloor\frac{n}{T}\rfloor)S(\lfloor\frac{m}{T}\rfloor)\times T\sum_{k\mid T}\mu(k)k \]

发现后半部分其实是可以预处理的，只需要求出 \(T\sum\limits_{k\mid T}\mu(k)k\) 的前缀和即可。令函数 \(f(n)=\sum\limits_{k\mid n}\mu(k)k\)，不难证明 \(f\) 是积性函数，所以可以在线性筛的时候顺便求。具体的，如果在用 \(i\) 筛 \(i\times p\) 时 \(x\) 有平方因子，即 \(p\mid i\)，因为 \(\mu(n)\) 在 \(n\) 有平方因子时为 \(0\)，所以 \(f(i\times p)=f(i)\)；如果没有平方银子，根据积性函数的性质，有 \(f(i\times p)=f(i)\times f(p)\)。时间复杂度 \(\mathcal{O}(T\sqrt n)\)。

//预处理
void init()
{
    f[1] = 1;
    for(int i = 2;i < N;i++)
    {
        if(!vis[i])p[++cnt] = i,f[i] = mod+1-i;
        for(int j = 1;j <= cnt&&i*p[j] < N;j++)
        {
            int now = i*p[j];vis[now] = 1;
            if(i%p[j]==0){f[now] = f[i];break;}
            f[now] = f[i]*f[p[j]]%mod;
        }
    }
    for(int i = 1;i < N;i++)f[i] = (f[i-1]+f[i]*i)%mod;
}
//计算
for(int i = 1,j;i <= n;i = j+1)
{
    j = min(n/(n/i),m/(m/i));
    (ans += (f[j]-f[i-1]+mod)*S(n/i)%mod*S(m/i)) %= mod;
}

[P3312 SDOI2014] 数表

给定 \(n,m,a\)，求 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^m \sigma(\gcd(i,j))[\sigma(\gcd(i,j))\le a]\)，\(T\) 组数据，\(n,m\le 10^5,T\le 2\times 10^4\)。

先考虑没有 \(a\) 的限制：

\[\begin{align} ans &= \sum_{i=1}^n\sum_{j=1}^m \sigma(\gcd(i,j)) \\ &= \sum_{d=1}^n \sigma(d) \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sum_{j=1}^{\lfloor\frac{m}{d}\rfloor} [\gcd(i,j)=1] \\ &= \sum_{d=1}^n \sigma(d) \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} \mu(i) \lfloor\frac{n}{di}\rfloor \lfloor\frac{m}{di}\rfloor \end{align} \]

枚举 \(T=di\)：

\[\begin{align} ans &= \sum_{T=1}^n \lfloor\frac{n}{T}\rfloor \lfloor\frac{m}{T}\rfloor \sum_{d\mid T} \sigma(d) \mu(\lfloor\frac{T}{d}\rfloor) \end{align} \]

令 \(f(x)=\sum\limits_{d\mid x} \sigma(d) \mu(\lfloor\frac{x}{d}\rfloor)\)，此时只有当 \(\sigma(d)\le a\) 时，才会对 \(f(x)\) 产生贡献。

于是可以按 \(a\) 从小到大对询问排序，每次暴力加入所有 \(\sigma(d)\le a\) 的 \(d\)，并更新 \(f(x)\)。由于求答案还需要知道 \(f\) 的前缀和，所以用树状数组维护即可。每个数插入的次数为调和级数，而插入一次时间复杂度为 \(\mathcal{O}(\log n)\)，所以总时间复杂度就是 \(\mathcal{O}(n\log^2 n+T\sqrt n\log n)\)。

杜教筛

介绍：

杜教筛可以在 \(\mathcal{O}(n^\frac 2 3)\) 的时间复杂度中求出一类积性函数的前缀和。假设 \(f\) 是一个积性函数，如果能找到另一个积性函数 \(g\) 使得 \(g\) 和\(f\ast g\) 的前缀和都能快速求出，那么就能用杜教筛求出 \(f\) 的前缀和。

比如：

可以在 \(\mathcal{O}(1)\) 的时间内求出 \(1\) 和 \(\varepsilon\) 的前缀和，而 \(\mu\ast I=\varepsilon\)，所以可以用杜教筛求出 \(\mu\) 的前缀和。
可以在 \(\mathcal{O}(1)\) 的时间内求出 \(1\) 和 \(Id\) 的前缀和，而 \(\varphi\ast I=Id\)，所以可以用杜教筛求出 \(\varphi\) 的前缀和。

杜教筛：

现在要求积性函数 \(f\) 的前缀和，令 \(S(n)=\sum\limits_{i=1}^n f(i)\)。

再找一个积性函数 \(g\)，则 \(f\ast g\) 的前缀和为：

\[\begin{align} \sum_{i=1}^n (f\ast g)(i) &= \sum_{i=1}^n\sum_{d\mid i} f(d)g(\frac i d) \\ &= \sum_{d=1}^n g(d) \sum_{i=1}^{\lfloor\frac n d\rfloor} f(i) \\ &= \sum_{d=1}^n g(d)S(\lfloor\frac n d\rfloor) \end{align} \]

接着考虑 \(g(1)S(n)\) 等于什么，发现：

\[\begin{align} g(1)S(n) &= \sum_{i=1}^n g(i)S(\lfloor\frac n i\rfloor)-\sum_{i=2}^n g(i)S(\lfloor\frac n i\rfloor) \\ &= \sum_{i=1}^n(f\ast g)(i)-\sum_{i=2}^n g(i)S(\lfloor\frac n i\rfloor) \end{align} \]

此时只需要找一个积性函数 \(g\) 使得 \(g\) 和 \(f\ast g\) 的前缀和都可以快速求出，就可以数论分块递归来求了。

伪代码：

ll sum_g(ll n);//g的前缀和
ll sum_fg(ll n);//f*g的前缀和
ll sum_f(ll n)
{
    ll ans = sum_fg(n);
    for(ll i = 2,j;i <= n;i = j+1)
    {
        j = n/(n/i);
        ans -= (sum_g(j)-sum_g(i-1))*sum_f(n/i);
    }
    return ans;
}

杜教筛是数论分块里面递归，时间复杂度可以看作 \(\mathcal{O}(n^\frac 3 4)\)，具体咋证的可以看以下式子感性理解：

\[\sum_{i=1}^{\sqrt n} \mathcal{O}(\sqrt i)+\mathcal{O}(\sqrt\frac n i)=\mathcal{O}(n^\frac 3 4) \]

其实可以预处理出前 \(m\) 个答案，然后再用杜教筛，时间复杂度就是：

\[\sum_{i=1}^{\lfloor\frac n m\rfloor}\mathcal{O}(\sqrt \frac n i) = \mathcal{O}(\frac {n}{\sqrt m}) \]

一般为了平均，当 \(m=n^\frac 2 3\) 时，时间复杂度也是 \(\mathcal{O}(n^\frac 2 3)\)。

\(\mu,\varphi\) 的前缀和

\(\mu\ast I=\varepsilon\)，而 \(I(n)\) 的前缀和就是 \(n\)，\(\varepsilon(n)\) 的前缀和就是 \(1\)。
\(\varphi\ast I=Id\)，而 \(Id(n)\) 的前缀和就是 \(\frac{n(n+1)}2\)。

代码中 \(smu,sphi\) 是提前筛好的 \(\mu\) 和 \(\varphi\) 的前缀和，\(Smu,Sphi\) 是记忆化。

ll sum_mu(int n)
{
    if(n < N)return smu[n];
    if(Smu[n])return Smu[n];
    ll ans = 1;
    for(ll i = 2,j;i <= n;i = j+1)
    {
        j = n/(n/i);
        ans -= (j-i+1)*sum_mu(n/i);
    }
    return Smu[n] = ans;
}
ll sum_phi(int n)
{
    if(n < N)return sphi[n];
    if(Sphi[n])return Sphi[n];
    ll ans = n*(n+1ll)/2;
    for(ll i = 2,j;i <= n;i = j+1)
    {
        j = n/(n/i);
        ans -= (j-i+1)*sum_phi(n/i);
    }
    return Sphi[n] = ans;
}

扩展：

求 \(f(n)=\varphi(i)\times i\) 的前缀和。

令 \(g=Id\)，则：

\[\begin{align} (f\ast g)(n) &= \sum_{d\mid n}(\varphi(d)\times d)\times \frac n d \\ &= n\sum_{d\mid n}\varphi(d) \\ &= n^2 \end{align} \]

所以 \(f\ast g\) 的前缀和就是 \(\frac{n(n+1)(2n+1)} 6\)。

PN 筛

咕咕咕

Min25 筛

咕咕咕

标签：lfloor,frac,ast,乌斯,sum,rfloor,mu,反演,莫比
From： https://www.cnblogs.com/max0810/p/18328775

莫比乌斯反演

莫比乌斯反演

前置芝士：数论分块

积性函数：

完全积性函数：

狄利克雷卷积：

性质：

莫比乌斯反演：\([n=1]=\sum\limits_{d\mid n}\mu(d)\)

欧拉反演：\(n=\sum\limits_{d\mid n}\varphi(d)\)

线性筛 \(\varphi\) 和 \(\mu\)

例题

最基本的应用

[P3327 SDOI2015] 约数个数和

P1829 Crash的数字表格

[P3312 SDOI2014] 数表

杜教筛

介绍：

杜教筛：

伪代码：

\(\mu,\varphi\) 的前缀和

扩展：

PN 筛

Min25 筛

相关文章

赞助商

阅读排行