莫比乌斯×狄利克雷

前情提要

需要掌握

1. $\mu$ 的定义及求法。
2. 大型运算符交换顺序。

引入

定义

1. $\forall n\in N^*$ ，一定有 $n=\prod\limits_{i=1}^qp_i^{a_i}$，
   对此定义 $\mu(n)=\begin{cases}0&n 含平方因子\\(-1)^q&otherwise\end{cases}$。
2. 定义元函数 $\epsilon(n)=[n=1]=\begin{cases}1&n=1\\0&n\not=1\end{cases}$。
3. $\mathrm{Id}_k(x)=x^k$。

公式

1. $\left\lfloor{\left\lfloor{i\over j}\right\rfloor\over k}\right\rfloor=\left\lfloor{i\over jk}\right\rfloor$。

积性函数

积性函数的线性递推

$$f(n)=\begin{cases}1&n=1\\g(n)&n\not=1 \land n=\mathrm{PA}(n)\\f(\mathrm{PA}(n))f({n\over \mathrm{PA}(n)})&n\not=1 \land n\not=\mathrm{PA}(n)\end{cases}$$

简介

莫比乌斯

莫比乌斯函数

$$\mu(x)$$

莫比乌斯反演

$$T(f)(n)=\sum_{d|n} f(d),R(f)(n)=\sum_{d|n} \mu\left({n\over d}\right) f(d)$$

莫比乌斯的性质

$$\epsilon(x)=\sum_{d|x} \mu(d)$$

狄利克雷

狄利克雷卷积

$$h=f*g\Leftrightarrow h(x)=\sum_{d|x} f(d)g\left({x\over d}\right)$$

若 $f,g$ 为积性函数，则 $h$ 为积性函数。

狄利克雷卷积的性质

$$\mathrm{Id}_k(x)=x^k$$

1. 交换律：$f*g=g*f$。
2. 结合律：$(f*g)*h=f*(g*h)$。
3. 分配率：$f*(g+h)=f*g+f*h$。
4. 单位元：$\epsilon*f=f$。
5. 逆元：若 $f*g=\epsilon$ ，那么称 $f$ 和 $g$ 互为逆元，即 $f=g^{-1},g=f^{-1}$。
6. 若 $f$ 和 $g$ 为积性函数，则 $f*g$ 也为积性函数，$f^{-1}$ 也是积性函数。
7. 若 $f*g=h$，则 $\mathrm{Id}_kf*\mathrm{Id}_kg=\mathrm{Id}_kh$。
   证明如下： $\begin{aligned}&\mathrm{Id}_kf*\mathrm{Id}_kg(n)\\=&\sum\limits_{d|n} f(d)g({n\over d})\mathrm{Id}_k(d)\mathrm{Id}_k({n\over d})\\=&\sum\limits_{d|n} f(d)g({n\over d})\mathrm{Id}_k(d{n\over d})\\=&\mathrm{Id}_k(n)\sum\limits_{d|n} f(d)g({n\over d})\\=&\mathrm{Id}_k(n)h(n)\end{aligned}$
8. 特别地，当 $h(n)=\sum\limits_{d|n}f(d)g(d)$ ，若 $f$ 和 $g$ 为积性函数，$h$ 也为积性函数，证明如下：
   设 $c(d)=f(d)g(d)$ ，因为 $f$ 和 $g$ 为积性函数，所以直积后仍为积性函数，
   而 $h(n)=\sum\limits_{d|n}c(d)=c*\mathrm{Id}_0$，所以 $h$ 也为积性函数。

莫比乌斯×狄利克雷

$$T(f)=f*\mathrm{Id}_0,R(f)=f*\mu$$ $$T(R(f))=R(T(f))=f$$

常见形式与例子

看不懂的，配套下文的技巧观看。

模板 $1$：函数套 $\gcd$

$$\begin{aligned} &\sum_{i=1}^{n} \sum_{j=1}^{m} f\left(\gcd\left(i,j\right)\right) & 原式\\ =&\sum_{d=1}^{\min\left\{n,m\right\}}f(d) \sum_{i=1}^{\left\lfloor {n\over d}\right\rfloor} \sum_{j=1}^{\left\lfloor {m\over d}\right\rfloor}\left[\gcd\left(i,j\right)=1\right] & 枚举 \gcd 的结果 d\\ =&\sum_{d=1}^{\min\left\{n,m\right\}}f(d) \sum_{i=1}^{\left\lfloor {n\over d}\right\rfloor} \sum_{j=1}^{\left\lfloor {m\over d}\right\rfloor} \sum_{k|i\land k|j} \mu\left(k\right) & 莫比乌斯函数的性质\\ =&\sum_{d=1}^{\min\left\{n,m\right\}}f(d) \sum_{k=1}^{\min\left\{\left\lfloor {n\over d}\right\rfloor,\left\lfloor {m\over d}\right\rfloor\right\}}\mu\left(k\right) \sum_{i=1}^{\left\lfloor {n\over kd}\right\rfloor} \sum_{j=1}^{\left\lfloor {m\over kd}\right\rfloor} 1 & 交换大型运算符位置\\ =&\sum_{d=1}^{\min\left\{n,m\right\}}f(d) \sum_{k=1}^{\min\left\{\left\lfloor {n\over d}\right\rfloor,\left\lfloor {m\over d}\right\rfloor\right\}}\mu\left(k\right) \left\lfloor {n\over kd}\right\rfloor \left\lfloor {m\over kd}\right\rfloor & 易得\\ =&\sum_{t=1}^{\min\left\{n,m\right\}} \sum_{k|t}f\left({t\over k}\right)\mu\left(k\right) \left\lfloor {n\over t}\right\rfloor \left\lfloor {m\over t}\right\rfloor & 换元令 t=kd\\ =&\sum_{t=1}^{\min\left\{n,m\right\}} \left\lfloor {n\over t}\right\rfloor \left\lfloor {m\over t}\right\rfloor \sum_{k|t}f\left({t\over k}\right)\mu\left(k\right) \end{aligned}$$

模板 $2$：函数乘函数乘函数套 $\gcd$

$$\begin{aligned} &\sum_{i=1}^{n} \sum_{j=1}^{m} g(i)h(j)f\left(\gcd\left(i,j\right)\right) & 原式\\ =&\sum_{d=1}^{\min\left\{n,m\right\}}f(d) \sum_{i=1}^{\left\lfloor {n\over d}\right\rfloor} g(i) \sum_{j=1}^{\left\lfloor {m\over d}\right\rfloor} h(j) \left[\gcd\left(i,j\right)=1\right] & 枚举 \gcd 的结果 d\\ =&\sum_{d=1}^{\min\left\{n,m\right\}}f(d) \sum_{i=1}^{\left\lfloor {n\over d}\right\rfloor}g(i) \sum_{j=1}^{\left\lfloor {m\over d}\right\rfloor}h(j) \sum_{k|i\land k|j} \mu\left(k\right) & 莫比乌斯函数的性质\\ =&\sum_{d=1}^{\min\left\{n,m\right\}}f(d) \sum_{k=1}^{\min\left\{\left\lfloor {n\over d}\right\rfloor,\left\lfloor {m\over d}\right\rfloor\right\}}\mu\left(k\right) \sum_{i=1}^{\left\lfloor {n\over kd}\right\rfloor} h(i) \sum_{j=1}^{\left\lfloor {m\over kd}\right\rfloor} g(j) & 交换大型运算符位置\\ =&\sum_{t=1}^{\min\left\{n,m\right\}} \sum_{k|t}f\left({t\over k}\right)\mu\left(k\right) \sum_{i=1}^{\left\lfloor {n\over t}\right\rfloor} h(i) \sum_{j=1}^{\left\lfloor {m\over t}\right\rfloor} g(j) & 换元令 t=kd\\ =&\sum_{t=1}^{\min\left\{n,m\right\}} \sum_{i=1}^{\left\lfloor {n\over t}\right\rfloor} h(i) \sum_{j=1}^{\left\lfloor {m\over t}\right\rfloor} g(j) \sum_{k|t}f\left({t\over k}\right)\mu\left(k\right) \end{aligned}$$ $$\sum_{i=1}^n{\sum_{j=1}^{m}\mathrm{lcm}(i,j)}$$

模板 $3$：多要求

$$\color{purple}{终极模板：见招拆招}$$ $$\begin{aligned} \sum_{t=1}^{\min\limits_{l=1}^{n}{a_l}}\left(\sum_{k|t}f\left({t\over k}\right)\mu\left(k\right)\right)\prod\limits_{p=1}^{n}\sum_{i=1}^{\left\lfloor {a_p\over t} \right\rfloor} g_p(i) \end{aligned}$$

模板 $4$：$\gcd$ 乘积

$$\begin{aligned} &\prod\limits_{i=1}^{n}\prod\limits_{j=1}^{m}f(\gcd(i,j))\\ =&\prod_{d=1}^{\min\{n,m\}} f(d)^{ \sum\limits_{i=1}^{\left\lfloor{n\over d}\right\rfloor} \sum\limits_{j=1}^{\left\lfloor{m\over d}\right\rfloor} [\gcd(i,j)=1] }\\ =&\prod_{d=1}^{\min\{n,m\}} f(d)^{ \sum\limits_{i=1}^{\left\lfloor{n\over d}\right\rfloor} \sum\limits_{j=1}^{\left\lfloor{m\over d}\right\rfloor} \sum\limits_{k|i\land k|j} \mu(k) }\\ =&\prod_{d=1}^{\min\{n,m\}} f(d)^{ \sum\limits_{k=1}^{\min\left\{ \left\lfloor{n\over d}\right\rfloor \left\lfloor{m\over d}\right\rfloor \right\}} \mu(k) \left\lfloor{n\over kd}\right\rfloor \left\lfloor{m\over kd}\right\rfloor }\\ =& \prod_{t=1}^{\min\{n,m\}} \prod_{d|t} f(d)^{ \mu({t\over d}) \left\lfloor{n\over t}\right\rfloor \left\lfloor{m\over t}\right\rfloor }\\ =& \prod_{t=1}^{\min\{n,m\}} \left(\prod_{d|t} f(d)^{ \mu({t\over d}) }\right) ^{ \left\lfloor{n\over t}\right\rfloor \left\lfloor{m\over t}\right\rfloor } \end{aligned}$$

求解技巧

技巧 $1$：枚举答案

$$\begin{aligned} &\sum_{i=1}^{n} \sum_{j=1}^{m} f\left(\gcd\left(i,j\right)\right) \\ =&\sum_{d=1}^{\min\left\{n,m\right\}}f(d) \sum_{i=1}^{n} \sum_{j=1}^{m}\left[\gcd\left(i,j\right)=d\right]\\ \end{aligned}$$

技巧 $2$：构造元函数

$$\begin{aligned} &\sum_{d=1}^{\min\left\{n,m\right\}}f(d) \sum_{i=1}^{n} \sum_{j=1}^{m}\left[\gcd\left(i,j\right)=d\right]\\ =&\sum_{d=1}^{\min\left\{n,m\right\}}f(d) \sum_{i'=1}^{\left\lfloor {n\over d}\right\rfloor} \sum_{j'=1}^{\left\lfloor {m\over d}\right\rfloor}\left[\gcd\left(i',j'\right)=1\right]\\ =&\sum_{d=1}^{\min\left\{n,m\right\}}f(d) \sum_{i=1}^{\left\lfloor {n\over d}\right\rfloor} \sum_{j=1}^{\left\lfloor {m\over d}\right\rfloor} \sum_{k|i\land k|j} \mu\left(k\right) \end{aligned}$$ $$\begin{aligned} &\sum_{i=1}^n{\sum_{j=1}^{m}d(ij)}\\ =&\sum_{i=1}^n{\sum_{j=1}^{m}\sum_{u|i}{\sum_{v|j}{[\gcd(u,v)=1]}}}\\ =&\sum_{u=1}^n\sum_{v=1}^{m}[\gcd(u,v)=1]\sum_{u|i}\sum_{v|j}1\\ =&\sum_{u=1}^n\sum_{v=1}^{m}[\gcd(u,v)=1]\left\lfloor{n\over u}\right\rfloor\left\lfloor{m\over v}\right\rfloor\\ =&\sum_{u=1}^n\sum_{v=1}^{m}\left\lfloor{n\over u}\right\rfloor\left\lfloor{m\over v}\right\rfloor\sum_{d|i\land d|j}{\mu(d)}\\ \end{aligned}$$

技巧 $3$：交换大型运算符+换元

$$\begin{aligned} &\sum_{d=1}^{\min\left\{n,m\right\}}f(d) \sum_{i=1}^{\left\lfloor {n\over d}\right\rfloor} \sum_{j=1}^{\left\lfloor {m\over d}\right\rfloor} \sum_{k|i\land k|j} \mu\left(k\right)\\ =&\sum_{d=1}^{\min\left\{n,m\right\}}f(d) \sum_{k=1}^{\min\left\{\left\lfloor {n\over d}\right\rfloor,\left\lfloor {m\over d}\right\rfloor\right\}}\mu\left(k\right) \sum_{i=1}^{\left\lfloor {n\over kd}\right\rfloor} \sum_{j=1}^{\left\lfloor {m\over kd}\right\rfloor} 1\\ =&\sum_{d=1}^{\min\left\{n,m\right\}}f(d) \sum_{k=1}^{\min\left\{\left\lfloor {n\over d}\right\rfloor,\left\lfloor {m\over d}\right\rfloor\right\}}\mu\left(k\right) \left\lfloor {n\over kd}\right\rfloor \left\lfloor {m\over kd}\right\rfloor\\ =&\sum_{d=1}^{\min\left\{n,m\right\}} \sum_{k=1}^{\min\left\{\left\lfloor {n\over d}\right\rfloor,\left\lfloor {m\over d}\right\rfloor\right\}}f(d)\mu\left(k\right) \left\lfloor {n\over kd}\right\rfloor \left\lfloor {m\over kd}\right\rfloor\\ =&\sum_{t=1}^{\min\left\{n,m\right\}} \sum_{k|t}f\left({t\over k}\right)\mu\left(k\right) \left\lfloor {n\over t}\right\rfloor \left\lfloor {m\over t}\right\rfloor\\ =&\sum_{t=1}^{\min\left\{n,m\right\}} \left\lfloor {n\over t}\right\rfloor \left\lfloor {m\over t}\right\rfloor \sum_{k|t}f\left({t\over k}\right)\mu\left(k\right) \end{aligned}$$ $$\begin{aligned} &\sum_{u=1}^n\sum_{v=1}^{m}\left\lfloor{n\over u}\right\rfloor\left\lfloor{m\over v}\right\rfloor\sum_{d|i\land d|j}{\mu(d)}\\ =&\sum_{d=1}^{\min\{n,m\}}{\mu(d)\sum_{d|i\land i\le n}{\left\lfloor {n\over i}\right\rfloor}\sum_{d|j\land j\le m}{\left\lfloor {m\over j}\right\rfloor}}\\ =&\sum_{d=1}^{\min\{n,m\}}{\mu(d) \sum_{i=1}^{\left\lfloor{n\over d}\right\rfloor}{\left\lfloor {n\over id}\right\rfloor} \sum_{j=1}^{\left\lfloor{m\over d}\right\rfloor}{\left\lfloor {m\over jd}\right\rfloor} }\\ \end{aligned}$$

技巧 $4$：快速预处理

技巧 $5$：换眼光看式子

$$\begin{aligned} &\sum_{d=1}^{\min\{n,m\}}{\mu(d) \sum_{i=1}^{\left\lfloor{n\over d}\right\rfloor}{\left\lfloor {n\over id}\right\rfloor} \sum_{j=1}^{\left\lfloor{m\over d}\right\rfloor}{\left\lfloor {m\over jd}\right\rfloor} }\\ =&\sum_{d=1}^{\min\{n,m\}}{\mu(d) \sum_{i=1}^{\left\lfloor{n\over d}\right\rfloor}{\left\lfloor {\left\lfloor{n\over d}\right\rfloor\over i}\right\rfloor} \sum_{j=1}^{\left\lfloor{m\over d}\right\rfloor}{\left\lfloor {\left\lfloor{m\over d}\right\rfloor\over j}\right\rfloor} } \end{aligned}$$

技巧 $6$：无关项分别求解

$$\prod_{i=1}^{A}{\prod_{j=1}^{B}{\prod_{k=1}^{C}{\left(\frac{\mathrm{lcm}(i,j)}{\gcd(i,k)}\right)^\alpha}}}$$ $${ \left( \prod\limits_{i=1}^{A} \prod\limits_{j=1}^{B} \prod\limits_{k=1}^{C} i^\alpha \right)\left( \prod\limits_{i=1}^{A} \prod\limits_{j=1}^{B} \prod\limits_{k=1}^{C} j^\alpha \right) \over \left( \prod\limits_{i=1}^{A} \prod\limits_{j=1}^{B} \prod\limits_{k=1}^{C} \gcd(i,j)^\alpha \right) \left( \prod\limits_{i=1}^{A} \prod\limits_{j=1}^{B} \prod\limits_{k=1}^{C} \gcd(i,k)^\alpha \right) }$$

技巧 $7$：对数反演

技巧 $8$：积分估值