莫比乌斯反演学习笔记

MarchKid_Joe · 2023-01-06 18:13:49 · 个人记录

莫比乌斯反演

std 文件

目录

• std文件
• 筛法
  • Eratosthenes 筛
  • Euler 筛
  • 杜教筛
• 积性函数
• 数论分块
  • 单元数论分块
  • 二元数论分块
• 狄利克雷卷积
  • 定义
  • 重要结论
  • 狄利克雷卷积
    • 狄利克雷前缀和
    • 狄利克雷后缀和
    • 逆狄利克雷前缀和
    • 逆狄利克雷后缀和
• 积性函数
  • 积性函数
  • 莫比乌斯函数
  • 欧拉函数
  • 约数个数
  • 约数和
  • 恒等函数
• 莫比乌斯反演
  • 反演结论
  • 证明
• 欧拉反演
  • 反演结论
  • 证明
• Problem
  • Question from 0 to 16
• 链接
• 重题
• 幽灵乐团
• 常用套路
  • 枚举 \gcd
  • 数论分块
  • 透彻了解积性函数的定义
  • 换元替换枚举项
  • 枚举倍数
  • 狄利克雷卷积和前缀和
  • 数据结构优化
  • 筛法
  • 根号分治
• 后言

筛法

Eratosthenes 筛（埃氏筛法）

描述

Eratosthenes 筛法，最简单的筛法，具体过程是每筛到一个素数，便把它的整数倍标记，时间复杂度 O(n\log\log n)。

性质及优点

每个合数会被其所有质因数筛到；每个合数第一次会被其最小的质因数筛到。

优点：因为没有取模运算，常数较小，在小范围内可能比 O(n) 线性筛快。

Code

void Eratosthenes(int n)
{
    vis[1] = true;
    for (int i = 2 ; i <= n ; i ++)
    {
        if (! vis[i])
            prime[++ cnt] = i;
        for (int j = i * 2 ; j <= n ; j += i)
            vis[j] = true;
    }
}

Euler 筛（线性筛）

描述

Euler 筛，便是我们常用的筛法，可以在线性时间复杂度内快速筛出素数和积性函数，时间复杂度 O(n)。

性质

每个合数仅会被它的最小质因子筛一次。这个性质很重要，是筛积性函数所必须要了解的。

Code

void Euler(int n)
{
    vis[1] = true;
    for (int i = 2 ; i <= n ; i ++)
    {
        if (! vis[i])
            prime[++ cnt] = i;
        for (int j = 1 ; j <= cnt && i * prime[j] <= n ; j ++)
        {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
}

杜教筛

引入

建议放到后面看，只是因为是筛法就扔到前面了。

对于很大的数据范围无法线性处理，就有了杜教筛这种非线性筛法。

设 f(n) 为要求的函数，g(n) 为参与卷积的函数，S(n)=\displaystyle\sum_{i=1}^{n}f(i)。

杜教筛的大概流程：寻找一个参与卷积的积性函数，先线性筛一部分需要的积性函数的前缀和，然后采用记忆化的方式求解大数据范围的前缀和。

证明

然后考虑 g(1)S(n) 如何求：

结论

积性函数

积性函数

定义

1. 积性函数

   函数 f(n)，满足 f(1) = 1 且 \forall x,y\in N^*，\gcd(x,y) = 1，有 f(x*y)=f(x)*f(y)，则 f(n) 为积性函数。

   性质：

   f(\prod{p_i^{k_i}})=\prod f({p_i^{k_i}})

2. 完全积性函数

   函数 f(n)，满足 f(1) = 1 且 \forall x,y\in N^*，有 f(x*y)=f(x)*f(y)，则 f(n) 为完全积性函数。

   性质：

   f(\prod{p_i^{k_i}})=\prod f({p_i})^{k_i}

常见的积性函数

莫比乌斯函数

定义

性质

线性筛 \mu

Code

void Euler(int n)
{
    mu[1] = 1;
    vis[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            p.emplace_back(i);
            mu[i] = -1;
        }
        for (int j = 0; j < p.size() && i * p[j] <= n; j++)
        {
            vis[i * p[j]] = true;
            if (i % p[j] == 0)
            {
                mu[i * p[j]] = 0;
                break;
            }
            mu[i * p[j]] = mu[i] * mu[p[j]];
        }
    }
}

欧拉函数

定义

性质

线性筛 \varphi

Code

void Euler(int n)
{
    phi[1] = 1;
    vis[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            p.emplace_back(i);
            phi[i] = i - 1;
        }
        for (int j = 0; j < p.size() && i * p[j] <= n; j++)
        {
            vis[i * p[j]] = true;
            if (i % p[j] == 0)
            {
                phi[i * p[j]] = phi[i] * p[j];
                break;
            }
            phi[i * p[j]] = phi[i] * phi[p[j]];
        }
    }
}

约数个数

定义

线性筛 \tau

设 \tau 为 f，需要辅助数组为 g。

记 g(n) 为 n 最小质因子的次幂。

Code

void Euler(int n)
{
    f[1] = 1;
    g[1] = 1;
    vis[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            p.emplace_back(i);
            g[i] = 1;
            f[i] = 2;
        }
        for (int j = 0; j < p.size() && i * p[j] <= n; j++)
        {
            vis[i * p[j]] = true;
            if (i % p[j] == 0)
            {
                g[i * p[j]] = g[i] + 1;
                f[i * p[j]] = f[i] / (g[i] + 1) * (g[i * p[j]] + 1);
                break;
            }
            g[i * p[j]] = 1;
            f[i * p[j]] = f[i] * f[p[j]];
        }
    }
}

约数和

定义

线性筛 \sigma

设 \sigma 为 f，需要辅助数组为 g。

记 g(n) 为 \displaystyle\sum_{i=0}p^i，p 为 n 的最小质因子。

Code

void Euler(int n)
{
    g[1] = 1;
    f[1] = 1;
    vis[1] = true;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            p.emplace_back(i);
            g[i] = i + 1;
            f[i] = i + 1;
        }
        for (int j = 0; j < p.size() && i * p[j] <= n; j++)
        {
            vis[i * p[j]] = true;
            if (i % p[j] == 0)
            {
                g[i * p[j]] = g[i] * p[j] + 1;
                f[i * p[j]] = f[i] / g[i] * g[i * p[j]];
                mu[i * p[j]] = 0;
                break;
            }
            g[i * p[j]] = p[j] + 1;
            f[i * p[j]] = f[i] * f[p[j]];
        }
    }
}

恒等函数

定义

线性筛 \operatorname{id_k}

Code

void Euler(int n)
{
    idk[1] = 1;
    vis[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            p.emplace_back(i);
            idk[i] = pow(i, k);
        }
        for (int j = 0; j < p.size() && i * p[j] <= n; j++)
        {
            vis[i * p[j]] = true;
            idk[i * p[j]] = idk[i] * idk[p[j]];
            if (i % p[j] == 0)
                break;
        }
    }
}

数论分块

引入

数论分块是数论中经常用到的优化方式，可以将复杂度由 O(n) 优化至 O(\sqrt{n})。对于 \lfloor\frac{n}{i}\rfloor,i\in[1,n]，会发现一段区间的贡献是相等的，可以一并计算。

对于 l\in[1,n]，当 r=\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor 时，区间 [l,r] 的贡献是相等的，因此可以用数论分块。

证明

证明之前，先了解一个结论:

要满足 \lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{j}\rfloor，假设 i,j 位于的相同贡献的块左右端点分别为 l,r，对于左端点为 l，此时 r 便为 \lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor，i\in[l,r] 时结果相同。

证明:

由此证得右端点 r=\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor。

单元数论分块

求解形如这种形式的式子：

for (int l = 1, r; l <= n; l = r + 1)
{
    r = n / (n / l);
    \\doing something.
    ans += (r - l + 1) * (n / l);
}

二元数论分块

求解形如这种形式的式子：

for (int l = 1, r; l <= n; l = r + 1)
{
    r = min(n / (n / l), m / (m / l));
    \\doing something.
    ans += (r - l + 1) * (n / l) * (m / l);
}

狄利克雷卷积

定义

等价于：

重要结论

狄利克雷卷积

假设 f(n) 已知，g(n) 未知（下列代码中 g 的初始值为 f）。

狄利克雷前缀和

for(prime:begin->end)
    for(i:1->n/prime)
        g[i*prime]+=g[i];

狄利克雷后缀和

for(prime:begin->end)
    for(i:n/prime->1)
        g[i]+=g[i*prime];

逆狄利克雷前缀和

for(prime:end->begin)
    for(i:n/prime->1)
        g[i*prime]-=g[i];

逆狄利克雷后缀和

for(prime:end->begin)
    for(i:1->n/prime)
        g[i]-=g[i*prime];

莫比乌斯反演

反演结论

证明：

欧拉反演

反演结论

证明：

Problem

序

在一切开始之前，为了方便，以下的所有题目默认 n\lt m。

Question 0

题目

前言

一切从这里开始，通过这道题目，学会枚举 \gcd 以及运用 \mu 反演。

了解一个重要的等价关系：

算法

证明

直接 O(n) 线性筛 \mu 然后求 \mu 的前缀和，然后可以做到单次询问 O(\sqrt{n}) 数论分块求解。顺便提一下：\gcd(n,0)=n。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int> p;
bitset<N> vis;
int mu[N];
int sum[N];
int n, m;
void Euler(int n)
{
    mu[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            p.emplace_back(i);
            mu[i] = -1;
        }
        for (int j : p)
        {
            if (i * j > n) break;
            vis[i * j] = true;
            if (i % j == 0) {mu[i * j] = 0;break;}
            mu[i * j] = -mu[i];
        }
    }
}
void Initial(int n)
{
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + mu[i];
}
signed main()
{
    cin >> n >> m;
    Euler(max(n, m));
    Initial(max(n, m));
    int ans = 0;
    for (int l = 1, r; l <= min(n, m); l = r + 1)
    {
        r = min(n / (n / l), m / (m / l));
        ans += (sum[r] - sum[l - 1]) * (n / l) * (m / l);
    }
    cout << ans;
    return 0;
}

Question 1

题目

前言

通过这道题目，对于整除的限制，学会改变 \sum 的枚举方式，直接枚举倍数。

算法

证明

第二步变换就相当于直接枚举 k 的倍数，即 i\gets{ik},j\gets{jk}，发现最后的式子可以二元数论分块，O(n) 线性筛 \mu 后预处理 \mu 的前缀和，每次求解 O(\sqrt{n})。

Question 2

题目

前言

通过这道题目，掌握莫比乌斯反演推演式子的重要方法：换元。

算法

• 换元

证明

直接继承 \operatorname{Problem 1} 的结论：

直接枚举质数然后求解时间复杂度还不能接受，\operatorname{TLE}，还需要继续转化。

解释这一步换元的转化方式：既然要把 T=kd 提出来作为枚举项，则当 k\mid T 时，d=\frac{T}{k}。所以就化为了这个式子。

这个式子可以直接预处理出 \displaystyle\sum_{k\mid T\land k\in prime}\mu(\frac{T}{k})，只需要枚举每个质数 k 的倍数就行了，然后就可以二元数论分块，因为只有质数的倍数，预处理时间复杂度不会超过 O(n\ln{n})，单次求解时间复杂度 O(\sqrt{n})。

Question 3

题目

前言

通过这道题，了解新的反演方式：\varphi 反演。

算法

证明

本题使用 \varphi 反演，发现式子跟 \operatorname{Problem 0} 区别不大，只是将 \mu 改为了 \varphi，二元数论分块和预处理 \varphi 的前缀和即可 O(n) 预处理，单次查询 O(\sqrt{n})。

Question 4

题目

前言

学会分解 \sum。

算法

证明

这道题主要说如何拆这个 \sum，然后就是 \operatorname{Problem 1} 了，为了方便书写，此篇只说明如何拆 \sum，证明省去了限制条件。

记 f(n,m)=\displaystyle\sum_{i=1}^{n}\displaystyle\sum_{j=1}^{m}[\gcd(i,j)=k]。

本质是二维容斥：

然后把 f(n,m) 换成 \operatorname{Problem 1} 就解决了。

Question 5

题目

前言

了解 \operatorname{lcm} 的拆解方法：

学会使用狄利克雷前缀和优化时间复杂度。

算法

• 狄利克雷前缀和

证明

设 f(n,m)=\displaystyle\sum_{i=1}^{n}\displaystyle\sum_{j=1}^{m}ij，发现后半部分可以 O(1) 求：

设 g(n,m)=\displaystyle\sum_{i=1}^{n}\displaystyle\sum_{j=1}^{m}ij[\gcd(i,j)=1]，发现这一部分可以数论分块：

最后换元，发现数论分块套数论分块：

【拓展】狄利克雷前缀和优化做法

使用狄利克雷前缀和。

设：

得到原式等于：

因为 g(n)=\displaystyle\sum_{d\mid n}d\mu(d)=\displaystyle\sum_{d\mid n}f(d)，满足狄利克雷前缀和的条件，可以在 O(n\log\log n) 的时间内预处理出来，然后就可以整除分块，总体时间复杂度 O(n\log\log n+\sqrt{n})。

狄利克雷前缀和优化代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int> p;
bitset<N> vis;
int mu[N];
int sum[N];
int n, m;
inline void Euler(int n)
{
    mu[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            mu[i] = -1;
            p.emplace_back(i);
        }
        for (int j : p)
        {
            if (i * j > n) break;
            vis[i * j] = 1;
            if (i % j == 0) break;
            mu[i * j] = -mu[i];
        }
    }
}
inline void Initial(int n)
{
    for (int i = 1; i <= n; i++)
        sum[i] = mu[i] * i;
    for (int k : p)
        for (int i = 1; i * k <= n; i++)
            sum[i * k] += sum[i];
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i] * i + sum[i - 1];
}
inline int S(int x)
{
    return x * (x + 1) / 2;
}
signed main()
{
    cin >> n >> m;
    Euler(max(n, m));
    Initial(max(n, m));
    int ans = 0;
    for (int l = 1, r; l <= min(n, m); l = r + 1)
    {
        r = min(n / (n / l), m / (m / l));
        ans += (sum[r] - sum[l - 1]) * S(n / l) * S(m / l);
    }
    cout << ans;
    return 0;
}

Question 6

题目

前言

设 $S(n)=\displaystyle\sum_{i=1}^{n}\displaystyle\sum_{j=1}^{n}(i+j)^k$。考虑如何 $O(n)$ 递推。

大力展开：

$$
\begin{aligned}
S(n)
&=\displaystyle\sum_{i=1}^{n}\displaystyle\sum_{j=1}^{n}(i+j)^k\\
&=\displaystyle\sum_{i=1}^{n-1}\displaystyle\sum_{j=1}^{n-1}(i+j)^k+\displaystyle\sum_{i=1}^{n}(n+i)^k+\displaystyle\sum_{i=1}^{n-1}(i+n)^k\\
&=S(n-1)+\displaystyle\sum_{i=n+1}^{2n-1}i^k+\displaystyle\sum_{i=n+1}^{2n-1}i^k+(2n)^k\\
&=S(n-1)+2(\displaystyle\sum_{i=1}^{2n-1}\operatorname{id_k(i)}-\displaystyle\sum_{i=1}^{n}\operatorname{id_k(i)})+\operatorname{id_k(2n)}
\end{aligned}
$$

线性筛 $\operatorname{id_k}$ 求前缀和就行了，于是 $O(n)$ 递推出了所有 $S$。

2. \displaystyle\sum_{T=1}^{n}\displaystyle\sum_{d\mid T}^{n}\alpha(d)\mu(\frac{T}{d})dT^kS(\lfloor\frac{n}{T}\rfloor) $\displaystyle\sum_{T=1}^{n}\displaystyle\sum_{d\mid T}^{n}\alpha(d)\mu(\frac{T}{d})d$，直接枚举 $d$ 的倍数预处理，时间复杂度 $O(n\ln n),n\leqslant5\times 10^5$，直接祭掉。 考虑使用**逆狄利克雷后缀和**优化，时间复杂度 $O(n\log\log n)$： 逆狄利克雷后缀和，适用于处理，已知积性函数 $f$ 和正整数 $n$，需要求取积性函数 $g$： $$ g(n)=\displaystyle\sum_{d\mid n}f(d) $$ 对于本题，设 $f(n)=\mu^2(n)d,g(n)=\displaystyle\sum_{d\mid n}\mu^2(d)\mu(\frac{n}{d})d=\displaystyle\sum_{d\mid n}f(n)*\mu(\frac{n}{d})

   两边同时卷 1，得到:

   \begin{aligned} (g*1)(n) &=(f*(u*1))(n)\\ &=\displaystyle\sum_{d\mid n}g(d)=(f*\varepsilon)(n)\\ &=\displaystyle\sum_{d\mid n}g(d)=f(n)\\ \end{aligned}

   然后就可以逆狄利克雷后缀和优化求取，最后 g(n)\times \operatorname{id_k}(n) 就是前面那一部分，然后求 g(n)\times \operatorname{id_k}(n) 的前缀和后数论分块。

Question 14

题目

多组询问 1\leqslant T\leqslant 10^4,1\leqslant n\leqslant 10^5。

前言

本题将带来新的套路（当然对于莫比乌斯反演来说较阴间）：根号分治。这一部分可能比较困难。

突然让我想起来上面的那道题：

单组询问 1\leqslant n\leqslant 5\times 10^5。

然而下面这道题直接少一个函数，这题怕不是弱化版吧。

还记得那道题的式子这么长：

然而这道题的式子这么短，花费了不到 10 分钟就推出来了（这莫非就是黑题？）：

后来发现这两个式子都没办法处理多组询问。

算法

• 根号分治

证明

按照套路：

设：

不难发现 f 直接枚举倍数，时间复杂度 O(n\ln n)。

至于 g 将其拆开，也可以得到递推式：

空间限制：7\operatorname{MB}

模数：104857601

前言

本题用到了 \prod 转化为指数的方法。

这也是比较有意思的题目。主要就是那个时空限制，考虑枚举 \gcd：

遇到这个式子，直接对着指数莫反。

然后就：

没什么，就是全黑了而已。

不要紧，只需要：

• 把筛 \mu 的数组 \text{int}\to\text{short}。

• \text{bool}\to\text{bitset}

• 前缀和 sum 的数组 \text{int}\to\text{short}。因为我打表发现 1e6 以内的 \mu 的前缀和最大 311。

卡卡空间就可以 Accepted 了。当然，证明少不了。

算法

证明

指数部分套路反演：

数论分块即可，然后就可以求出：\displaystyle\prod_{d=1}^{n}d^{-2\sum_{i=1}^{n}\sum_{j=1}^{n}[\gcd(i,j)=d]}。

最后考虑前半部分：

总式子：

会用到的一个结论：(a\times inv(b))\bmod p =(a\bmod p)\times (inv(b)\bmod p)。

Question 16

题目

模数：23333

数据：1\leqslant n\leqslant5\times10^4,1\leqslant T\leqslant3\times10^4

前言

根号分治。

注意一点，遇到 \varphi(ij) 别着急，拆成这个 \frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))} 会让你陷入深渊，某个 XX 就把这个式子转化成了 O(n^7)。

一定不要忘了最基本的积性函数的性质：

然后开始证明。

算法

• 根号分治
• 基本的积性函数性质

证明

设：g(n,m)=\displaystyle\sum_{i=1}^{n}\varphi(im)，不难得到 g 的递推式：

时间复杂度 O(n\ln n)。

原式换元为：

总体时间复杂度 O(n\ln n + T\times n\log n)，时间复杂度不能接受。

考虑设置一个限制 S，对于小部分暴力，大部分数论分块。

设： f(n,m,x)=\displaystyle\sum_{d\mid x}\mu(d)g(d,n)g(d,m)

如果能全部预处理出来就离谱了。所以对于 \leqslant S 的部分我们预处理。

枚举 d 的倍数预处理就行了，注意 x 上界是 \lfloor\frac{limit}{\max(n,m)}\rfloor。

不太严谨的求边界的方法：

对于 (\lfloor\frac{m}{S}\rfloor,n] 进行数论分块，对于 [1,\lfloor\frac{m}{S}\rfloor] 直接暴力。

总体时间复杂度 O(n\ln n+(S+T)+S^2\log n+\sqrt{S}\log S)。

链接

题单

Problem 0:P2158 [SDOI2008] 仪仗队

Problem 1:P3455 [POI2007]ZAP-Queries

Problem 2:P2257 YY的GCD

Problem 3:P2398 GCD SUM

Problem 4:P2522 [HAOI2011]Problem b

Problem 5:P1829 [国家集训队]Crash的数字表格 / JZPTAB

Problem 6:P3327 [SDOI2015]约数个数和

Problem 7:P3768 简单的数学题

Problem 8:P4449 于神之怒加强版

Problem 9:P6810 「MCOI-02」Convex Hull 凸包

Problem 10:P3312 [SDOI2014]数表

Problem 11:P3704 [SDOI2017]数字表格

Problem 12:P8570 [JRKSJ R6] 牵连的世界

Problem 13:P6156 简单题

Problem 14:P4240 毒瘤之神的考验

Problem 15:P5221 Product

Problem 16:P5572 [CmdOI2019]简单的数论题

多倍经验

Problem 1:

• P4450 双亲数

Problem 2:

• P2568 GCD
• SP4491 PGCD - Primes in GCD Table

Problem 3:

• P1390 公约数的和
• P1447 [NOI2010] 能量采集
• UVA11417 GCD
• UVA11424 GCD - Extreme (I)
• UVA11426 拿行李（极限版） GCD - Extreme (II)
• SP3871 GCDEX - GCD Extreme
• SP19985 GCDEX2 - GCD Extreme (hard)

Problem 4:

• SP26017 GCDMAT - GCD OF MATRIX

Problem 5:

• AGC038C LCMs
• P3911 最小公倍数之和

Problem 15:

• P4917 天守阁的地板

Band（幽灵乐团）

前言

别忘了，仍然默认 n\leqslant m。

幽灵乐团最后提交 66 次，成功了，先整一道简单题目：

Solution

由于只有一组询问枚举 n 的约数即可暴力求 \varphi 即可。但是这个题并不是幽灵乐团，也不是幽灵乐团的前置知识。

题目

幽灵乐团由 3 个子问题构成。

Problem 1

将 \operatorname{lcm} 展开：

Solution

我们将这个子问题再化为孙子问题：

原问题变为：

• 线性筛 \mu 及其前缀和。

• 预处理 f_1，即阶乘。

• 对 g_1,h_1 数论分块。

Problem 2

Solution

仍然先展开 \operatorname{lcm}：

将子问题继续分开计算：

原问题化为：

• 预处理 f_2，即 f_2(n)=\prod_{i=1}^{n} i^i。

• 预处理 \operatorname{id_2}\times \mu 的前缀和，方便对 g_2 数论分块。

• 预处理 \prod_{i=1}^{n}i^{i^2} 的前缀积，方便对 h_2 数论分块。

Problem 3

Solution

仍然化为孙子问题。

先考虑分子部分，这部分相对简单。只是出现之前没有见过的东西，大力枚举三个数的 \gcd。注意，不保证 A\lt B\lt C，而且不要发挥假的人类智慧交换 A,B,C，Wrong Answer，所以我这次写 \min 函数了。

于是就可以数论分块解决了。

然后就看分母（坟墓）吧，这次没有大力枚举三个数的 \gcd，我采用两个两个枚举：

发现指数的后半部分是我们第一问所求的 g_1。

我们单独将指数的另一部分拿出来：\displaystyle\sum_{i=1}^{C}\gcd(n,i)，和最上面的那道题有点像，但是上界不一样：

这里出现了新套路，我们来证明一下：

原式子变为：

预处理 n 的倍数，然后求 d^{g_3(d,C)} 前缀积数论分块，查询一次 O(n\ln n+n^{0.75})，但是时间复杂度太大，瓶颈在于预处理，继续观察这个式子：\displaystyle\sum_{T\mid n}\varphi(T)\lfloor\frac{C}{T}\rfloor。

设：f(n,C)=\lfloor\frac{C}{n}\rfloor\varphi(n)，我们当前要求 g(n)=\displaystyle\sum_{i\mid n}\varphi(i)\lfloor\frac{C}{i}\rfloor=\displaystyle\sum_{i\mid n}f(i,C)。发现是狄利克雷前缀和的形式。

所以对于每个 C，我们可以在 O(n\log\log n) 的时间复杂度内处理出所有的 g_3，然后正常数论分块。

原问题化为：

• 线性筛 \varphi 和预处理 \varphi 的前缀和，方便对分子部分数论分块。

• 预处理 i^{\varphi(i)} 的前缀积，方便对分子部分数论分块。

• 每次询问对于 C 预处理 g_3 数组。然后处理 d^{g_3(d,C)} 前缀积，方便对分母部分数论分块。

Summary

只需要预处理：

• 对于子问题 3 每次预处理 g 数组。

然后：

• 子问题 1：数论分块套数论分块。

• 子问题 2：数论分块套数论分块。

• 子问题 3：狄利克雷前缀和，数论分块套数论分块。

两个数的：

多个数的：

这是必备的。

数论分块

对于一个变量集合 \{a\}，单元和多元都一样，这也是必备的。

对于 \prod 转换为指数上的 \sum

这也是必备的。

顺便提一嘴，\prod 的好处就是可以乱分裂：

透彻了解积性函数的定义

对于这些式子 \sum_{i=1}^{n}[\gcd(i,n)=1] 就是 \varphi(n) 了，可以直接省掉一个 \sum，这很重要啊。再比如 \sum_{i=1}^{n}[i\mid n] 就是 \sigma(n)。灵活化为积性函数，有时会使问题简单不少。

了解一些结论，方便拆式子：

别忘记了积性函数最基本的定义：f(ij)=f(i)\times f(j)\land\gcd(i,j)=1。

所以有时候吧，把式子拆为这样，更方便一点：

拆为这样，恐怕就无底洞了。

换元替换枚举项

也就是常说的 T=ds：

枚举倍数

用于预处理和化简式子：

枚举 d 的倍数预处理，时间复杂度 O(n\ln n)：

化简式子，记得枚举倍数时变 i\gets i\times d,j\gets j\times d：

狄利克雷卷积和前缀和

对 \displaystyle\sum_{d\mid n}f(d)g(\frac{n}{d}) 敏感，万一可以直接卷积成积性函数（(\mu*\operatorname{id}=\varphi)\qquad etc...）呢？

当然也要学会运用狄利克雷前缀和，时间复杂度非常优秀 O(n\log\log n)，比如最后这道幽灵乐团，A loser 差点就诞生了。

数据结构优化

对于某些限制了，像限制 \gcd 的大小的，各种神奇的函数大小的。可以离线询问，按照限制排序，每次查询之前先继承上一次的限制处理到现在询问的限制。一般是动态维护前缀和，用树状数组可以平衡预处理和询问，做到预处理和询问都是 O(\log n)；而直接暴力的话大概就是预处理 O(n)，询问 O(1)，显然不划算。

比如数表那个题：对于约数个数和 \sigma 和的限制 \sigma\leqslant a，最后化简出这么一个式子：

因为要整除分块，所以对于一个块的区间 [l,r]，\displaystyle\sum_{T=l}^{r}\displaystyle\sum_{d\mid T}\sigma(d)\mu(\frac{T}{d}) 是前缀和的形式，每次询问前只要维护 \sigma(x)\leqslant a 相应的贡献都加入 x 的倍数里面，然后就可以数论分块了。

筛法

1. 线性筛可以筛很多积性函数，包括一些化简式子时出现的一些奇怪的积性函数的乘积的形式 \mu(n)^2*\varphi(n)*\operatorname{id}(n)...（都可以筛，随便筛）。只要记住：

每个数只会被他的最小质因数筛一次。

2. 对于数据范围大的无法线性筛的，找到合适的积性函数，用杜教筛。

根号分治

这是莫比乌斯反演很阴间的做法，因为暴力会超时，全部预处理不仅超时还炸空间，需要设置边界 S。预处理 S 之内的部分，方便数论分块。对于大的部分 [\lfloor\frac{m}{S}\rfloor+1,n] 数论分块，小部分 [1,\lfloor\frac{m}{S}\rfloor] 暴力。

后言

因为文章太卡了，把代码全删了（原稿有代码，链接见下），如需要可以参考篇首文件 std。愿各位能够通过本篇例题讲解学到很多莫比乌斯反演的套路。

整完幽灵乐团，可能以后不会再写任何莫比乌斯反演的题解了。这不是终点，并不是永远不做相关的题。而是关于这一部分的文章就不需要了，因为文章达到了它的作用：琢磨完了这部分的套路，Oler 的时间有限，那就不需要再多浪费时间继续深究这部分了。莫比乌斯反演题有很多，但是套路基本就这些了。

Wordpress

Luogu莫比乌斯反演文章-原稿

从最开始的琢磨换元换枚举项琢磨了一下午到现在对于化简式子可以算是随便跳步，en，本蒟蒻还是有长进的。就这样了。愿广大 Oler 们能坚持自己理想，珍惜时间。

Finished：2022-10-07 11:20:54

Update：2023-01-06 17:39:22

END