摘要：莫反，贝尔数，多项式
引入
求（$T,n,m\le10^5$）：
$$\sum_{i=1}^{n}\sum_{j=1}^{m}\mathrm{Bell}_{gcd(i,j)}$$
前置
- 多项式全家桶
- Bell 数相关
- 莫反基础
莫反
把 $\mathrm{Bell}$ 抽象处理出来就是这个式子：
$$\sum_{i=1}^{n}\sum_{j=1}^{m}f(\gcd(i,j))$$
设 $n\ge m$：
$$\begin{aligned}&\sum_{i=1}^{n}\sum_{j=1}^{m}f(\gcd(i,j))\\=&\sum_{d=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{m}f(d)[\gcd(i,j)=d]\\=&\sum_{d=1}^{n}f(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}f(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{k|i}\sum_{k|j}\mu(k)\\=&\sum_{d=1}^{n}f(d)\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\sum_{k|i,i\le \lfloor\frac{n}{d}\rfloor}\sum_{k|j,j\le \lfloor\frac{m}{d}\rfloor}1\\=&\sum_{d=1}^{n}f(d)\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\left\lfloor\frac{n}{dk}\right\rfloor\left\lfloor\frac{m}{dk}\right\rfloor\\=&\sum_{d=1}^{n}\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}f(d)\mu(k)\left\lfloor\frac{n}{dk}\right\rfloor\left\lfloor\frac{m}{dk}\right\rfloor\\\end{aligned}$$
设 $t=dk$，$g=f\ast\mu$：
$$\sum_{t=1}^{n}g(t)\left\lfloor\frac{n}{t}\right\rfloor\left\lfloor\frac{m}{t}\right\rfloor$$
数论分块，$O(\sqrt n)$ 单次。
贝尔数
贝尔数以埃里克·坦普尔·贝尔命名，是组合数学中的一组整数数列。
贝尔三角形
递推式
$$B_{n}=\sum_{k=0}^{n-1}C_{n}^{k}B_{k}$$
e
模板：P5748 集合划分计数
e，这部分需要的前置有一点点多，就先咕了。
就是不想写。