预备知识：
- 数论函数：定义域为正整数的函数，如
- 单位函数：$\epsilon(n) = [n==1]$ 。
- 恒等函数：$id_k(n) = n^k$ ，$id_1(n)$ 通常简记为 $id(n)$ 。
- 常数函数：$1(n) = 1$ 。
- 除数函数：$\sigma_k(n) = \sum\limits_{d|n}d^k$ 。 $\sigma_0(n)$ 通常简记为 $d(n)$ 或 $r(n)$ ， $\sigma_1(n)$ 通常简记为 $\sigma(n)$ 。
- 欧拉函数：$\varphi(n) = \sum\limits_{i=1}^n[(i,n)==1]$ 。
- 莫比乌斯函数：$\mu(n)=\begin{cases}1&n=1\\0&\exists d>1,d^{2}\mid n\\(-1)^{\omega(n)}&\text{otherwise}\end{cases}$ ，其中 $\omega(n)$ 表示 $n$ 的本质不同质因子个数。
- 狄利克雷卷积：对于两个数论函数 $f(x)$ 和 $g(x)$ ，他们的狄利克雷卷积结果 $h(x)$ 定义为：$$h(x) = \sum \limits_{d|x}f(d)g(\frac{x}{d})=\sum \limits_{ab=x}f(a)g(b)$$ 可以简记为 $$h=f * g$$
- 狄利克雷卷积满足交换律，结合律，分配律。
- 莫比乌斯函数：
- 定义：$\mu(n)=\begin{cases}1&n=1\\0&\exists d>1,d^{2}\mid n\\(-1)^{\omega(n)}&\text{otherwise}\end{cases}$
- 性质：$\sum \limits_{d|n} \mu(d)= \begin{cases}1, & n=1, \ 0, & n \neq 1\end{cases}$ ，即 $\sum \limits_{d|n}\mu(d)=\epsilon(n),\mu * 1 = \epsilon$ ，证明如下
- 设 $n = \prod\limits_{i=1}^{k}p_i^{c_i},n’ = \prod\limits_{i=1}^{k}p_i$ ，那么 $\sum\limits_{d|n}\mu(d) = \sum\limits_{d|n’}\mu(d)=\sum\limits_{i=0}^k\binom{k}{i}·(-1)^i=(1+(-1))^k$ 。
- 根据二项式定理，易知该式子的值在 $k=0$ ，即 $n=1$ 时值为 $1$ ，否则为 $0$ ，即 $\sum \limits_{d|n}\mu(d)=\epsilon(n),\mu * 1 = \epsilon$ 。
- 推论：$[gcd(i, j)==1]=\sum\limits_{d|gcd(i,j)}\mu(d)$
例题：
求 $\sum \limits_{i=1}^{n} \sum \limits_{j=1}^{m} [gcd(i, j)=1]$ 。
解：
因为 $gcd(i, j)=1$ 时对答案才有贡献，于是我们可以直接将其替换为 $\epsilon(gcd(i, j))$ ，故原式化为$$\sum \limits_{i=1}^{n} \sum \limits_{j=1}^{m} \epsilon(gcd(i, j))$$
将 $\epsilon$ 函数展开得到，$$\sum \limits_{i=1}^{n} \sum \limits_{j=1}^{m} \sum \limits_{d|gcd(i,j)}\mu(d)$$
变换求和顺序，先枚举 $d|gcd(i,j)$ 得到：$$\sum \limits_{d=1}\mu(d)\sum \limits_{i=1}^{n} [d|i]\sum \limits_{j=1}^{m} [d|j]$$
易知 $1\sim n$ 中 $d$ 的倍数有 $\lfloor \frac{n}{d}\rfloor$ 个，故原式化为 $$\sum \limits_{d=1}^{min(n,m)}\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor$$
很显然，式子可以用数论分块求解，时间复杂度 $O(n + T\sqrt{n})$ 。
莫比乌斯反演法
莫比乌斯反演公式：
如果 $$g(d)=\sum\limits_{k:d|k}f(k)$$
那么 $$f(d)=\sum\limits_{k:d|k}\mu(\frac{k}{d})g(k)$$
例题：
给定区间 $[L, R]$，求其中所有非空子集 $S \subseteq [L,R]$，使得 $\gcd(S) = 1$ 的子集个数，答案对 $998244353$ 取模。题目链接
解：
我们不妨考虑一个更简单的问题，对于区间 $[1,n]$ ，求所有符合题意的非空子集 $S$ 。
我们可以把所有子集按照 $gcd$ 进行分类。$$\text{总集合数}=\sum\limits_{d=1}^{n}f(d)$$
其中 $f(d)$ 为所有 $\gcd(S)=d$ 的子集个数，显然每个子集的 $gcd$ 都属于某个 $d$ ，所以有 $$2^n-1=\sum\limits_{d=1}^{n}f(d)$$
如果某个子集 $S$ 的所有元素都能被 $d$ 整除， 那么 $\gcd(S)$ 一定是 $d$ 的倍数。
所以我们定义 $g(d)$ 为所有元素都能被 $d$ 整除的非空子集数。
显然有 $$g(d)=2^{\lfloor\frac{n}{d}\rfloor}-1$$
因为所有元素都能被 $d$ 整除的子集，其 $\gcd$ 可能是 $d, 2d, 3d, \cdots$
所以 $$g(d)=\sum\limits_{k:d|k}f(k)$$
这里我们可以使用莫比乌斯反演法，得到 $$f(d) = \sum\limits_{k:d|k}\mu(\frac{k}{d})g(k)$$
我们要的是 $f(1)$ ，直接计算即可 $$f(1)=\sum\limits_{d=1}^{n}\mu(d)(2^{\lfloor\frac{n}{d}\rfloor}-1)$$
推广到区间 $[L,R]$ ，很容易想到区间 $[L,R] \text{中}\gcd=1\text{的子集数量}$ 为 $$[1,R] \text{中}\gcd=1\text{的子集数量} – [1,L-1] \text{中}\gcd=1\text{的子集数量}$$
所以 $$ans = \sum\limits_{d=1}^{R}\mu(d)(2^{\lfloor\frac{R}{d}\rfloor-\lfloor\frac{L-1}{d}\rfloor}-1)$$
代码如下：
void solve() {
int L, R;
cin >> L >> R;
L--;
Z ans = 0;
int l = 1, r;
while (l <= R) {
r = R / (R / l);
if (l <= L) r = min(r, L / (L / l));
ans += (ksm(Z(2), R / l - L / l) - 1) * (sumMu(r) - sumMu(l - 1));
l = r + 1;
}
cout << ans << "\n";
}