浅谈——数论全家桶（二）

· · 算法·理论

写 \LaTeX 写疯了，点赞顶我上去吧。

狄利克雷卷积

什么是狄利克雷卷积？

狄利克雷卷积，英文名 \texttt{Dirichlet convolution}，也常说 \text{Dirichlet} 卷积。

狄利克雷卷积是定义在数论函数（定义域为自然数，值域为复数的函数）间的一种二元运算，常见的定义式：

(f\ast g)(n)=\displaystyle\sum_{d\mid n}f(d)g\left(\dfrac{n}{d}\right)=\sum_{xy=n}f(x)g(y)

常用的数论函数有哪些？

狄利克雷卷积是数论函数的重要运算。数论函数的许多性质都是通过这个运算挖掘出来的。 ::::success[单位函数 \varepsilon] 单位函数 \varepsilon 是莫比乌斯函数 \mu 和常数函数 \mathbf 1 的狄利克雷卷积：

\varepsilon=\mu\ast\mathbf 1\Leftrightarrow \varepsilon(n)=\displaystyle\sum_{d\mid n}\mu(d)\mathbf 1\left(\dfrac{n}{d}\right)=\sum_{d\mid n}\mu(d)

也有：

\varepsilon(n)= \begin{cases} 1 & n=1\\ 0 & n\neq 1(\text{otherwise}) \end{cases}
莫比乌斯反演就是利用 \varepsilon=\mu∗\mathbf 1 对数论函数恒等式进行变形。
::::success[幂函数 \mathrm{Id}_k]
幂函数 \mathrm{Id}_k(n)=n^k。
特别地，k=0 时为常数函数 \mathbf 1(n)=1，k=1 时为恒等函数 \mathrm{Id}(n)=n。
::::success[除数函数 \sigma_k]
除数函数 \sigma_k(n)=\displaystyle\sum_{d\mid n}d^k。

特别地，k=0 时为除数个数函数 \tau(n)=\displaystyle\sum_{d\mid n}1，k=1 时为除数和函数 \sigma(n)=\displaystyle\sum_{d\mid n}d。 :::success[除数个数函数 \tau] 除数个数函数 \tau 是常数函数 \mathbf 1 和它自身的狄利克雷卷积：

\tau=\mathbf 1\ast\mathbf 1\Leftrightarrow\tau(n)=\displaystyle\sum_{d\mid n}\mathbf 1(d)\mathbf 1\left(\dfrac{n}{d}\right)=\sum_{d\mid n}1
假设将 n 分解质因数为 n=p_1^{c_1}p_2^{c_2}\cdots p_x^{c_x}，则 \tau(n)=\displaystyle\prod_{i=1}^x(c_i+1)，证明显然就是每个质因数选几次（或不选）。
:::success[除数和函数 \sigma]
除数和函数 \sigma 是恒等函数 \mathrm{Id} 和常数函数 \mathbf 1的狄利克雷卷积：
\sigma=\mathrm{Id}\ast\mathbf 1\Leftrightarrow \sigma(n)=\displaystyle\sum_{d\mid n}\mathrm {Id}(d)\mathbf 1\left(\dfrac{n}{d}\right)=\sum_{d\mid n}d
假设将 n 分解质因数为 n=p_1^{c_1}p_2^{c_2}\cdots p_x^{c_x}，则 \sigma(n)=\displaystyle\prod_{i=1}^x(\sum_{j=0}^{c_i}p_i^j)，证明显然就是枚举每个因数然后相加。
:::
::::
::::success[欧拉函数 \varphi]
欧拉函数 \varphi 是恒等函数 \mathrm{Id} 和莫比乌斯函数 \mu 的狄利克雷卷积：
\varphi=\mathrm{Id}\ast\mu\Leftrightarrow\varphi(n)=\displaystyle\sum_{d\mid n}\mathrm{Id}(d)\mu\left(\dfrac{n}{d}\right)=\sum_{d\mid n}d\mu\left(\dfrac{n}{d}\right)
其余性质可见浅谈——数论全家桶（一）
::::
以上所提及的所有函数均为积性函数，特别地，单位函数 \varepsilon 和幂函数 \mathrm{Id_k} 为完全积性函数。
## 狄利克雷卷积有哪些性质？
以下设 f,g,h 均为数论函数。
::::success[性质 1]
> 狄利克雷卷积满足交换律：f\ast g=g\ast f。
:::info[证明]
(f\ast g)(n)=\displaystyle\sum_{xy=n}f(x)g(y)=\sum_{yx=n}f(y)g(x)=\sum_{xy=n}g(x)f(y)=(g\ast f)(n)
交换律得证。
::::
::::success[性质 2]
> 狄利克雷卷积满足结合律：(f\ast g)\ast h=f\ast(g\ast h)。
:::info[证明]
$$
\begin{align*}
((f\ast g)\ast h)(n)&=\displaystyle\sum_{xy=n}(f\ast g)(x)\cdot h(y)\
&=\displaystyle\sum{xy=n}(\sum{ab=x}f(a)g(b))h(y)\
&=\displaystyle\sum{xy=n}\sum{ab=x}f(a)g(b)h(y)\
&=\displaystyle\sum_{aby=n}f(a)g(b)h(y)\
&=\displaystyle\sum_{yab=n}f(y)g(a)h(b)\
&=\displaystyle\sum{yx=n}\sum{ab=x}f(y)g(a)h(b)\
&=\displaystyle\sum{yx=n}(\sum{ab=x}g(a)h(b))f(y)\
&=\displaystyle\sum_{yx=n}(g\ast h)(x)\cdot f(y)\
&=(f\ast(g\ast h))(n)
\end{align*}
$$
结合律得证。
::::
::::success[性质 3]
> 狄利克雷卷积满足分配律：(f+g)\ast h=f\ast h+g\ast h。
:::info[证明]
$$
\begin{align*}
((f+g)\ast h)(n)&=\displaystyle\sum_{xy=n}(f+g)(x)\cdot h(y)\
&=\displaystyle\sum_{xy=n}(f(x)+g(x))h(y)\
&=\displaystyle\sum_{xy=n}f(x)h(y)+g(x)h(y)\
&=\displaystyle\sum{xy=n}f(x)h(y)+\displaystyle\sum{xy=n}g(x)h(y)\
&=(f\ast h)(n)+(g\ast h)(n)\
&=(f\ast h+g\ast h)(n)
\end{align*}
$$
分配律得证。
:::
::::
至此，你可以将狄利克雷卷积看成实数乘法。
::::success[性质 4]
> 若 f,g 为积性函数，则 f\ast g 也是积性函数。
:::info[证明]
由条件已知 \gcd(x,y)=1,f(xy)=f(x)f(y),g(xy)=g(x)g(y)。

下面 \gcd(n,m)=1：

\begin{align*} (f\ast g)(n)\cdot(f\ast g)(m)&=\displaystyle\sum_{d_1\mid n}f(d_1)g\left(\dfrac{n}{d_1}\right)\cdot\sum_{d_2\mid m}f(d_2)g\left(\dfrac{m}{d_2}\right)\\ &=\displaystyle\sum_{d_1\mid n}\sum_{d_2\mid m}f(d_1)g\left(\dfrac{n}{d_1}\right)f(d_2)g\left(\dfrac{m}{d_2}\right)\\ &=\displaystyle\sum_{d_1\mid n}\sum_{d_2\mid m}f(d_1d_2)g\left(\dfrac{nm}{d_1d_2}\right)\\ &=\displaystyle\sum_{(d_1d_2)\mid (nm)}f(d_1d_2)g\left(\dfrac{nm}{d_1d_2}\right)\\ &=\displaystyle\sum_{d\mid(nm)}f(d)g\left(\dfrac{nm}{d}\right)\\ &=(f\ast g)(nm) \end{align*}

其中，d_1\mid n,d_2\mid m 合并成 (d_1d_2)\mid (nm) 的理由是 \gcd(n,m)=1，即 n,m 互质，所以 d_1,d_2 除了均为 1 的情况不可能相等。所以 d_1\mid n,d_2\mid m\Leftrightarrow(d_1d_2)\mid(nm)。完全等价。

经过狄利克雷卷积后的积性性得证。
::::
::::success[性质 5]
> f\ast\varepsilon=f，其中，\varepsilon(n)=[n=1] 是卷积单位元。
:::info[证明]
(f\ast\varepsilon)(n)=\displaystyle\sum_{xy=n}f(x)\varepsilon(y)
因为 \varepsilon(n)=[n=1]，所以当且仅当 y=1，即 x=n 时有贡献。显然：
(f\ast\varepsilon)(n)=f(n)\varepsilon(1)=f(n)
所以单位函数 \varepsilon 是狄利克雷卷积的单位元。
::::
::::success[性质 6]
> 当 f(1)\neq0 时，f\ast g=\varepsilon，则将 g 称为 f 的狄利克雷逆元（\texttt{Dirichlet inverse}），记作 g。
:::success[逆元 g 满足的递推公式推导]
首先考虑为什么 f(1)\neq0。
(f\ast g)(1)=\displaystyle\sum_{d\mid 1}f(d)g\left(\dfrac{1}{d}\right)=f(1)g(1)=\varepsilon(1)=1

所以 g(1)=\dfrac{1}{f(1)}，显然要使该等式有意义必须使 f(1)\neq0。这样我们就证明了前提条件。

然后考虑推导递推式。不妨计算 (f\ast g)(2)。

(f\ast g)(2)=\displaystyle\sum_{d\mid 2}f(d)g\left(\dfrac{2}{d}\right)=f(1)g(2)+f(2)g(1)=\varepsilon(2)=0

所以 g(2)=-\dfrac{f(2)g(1)}{f(1)}。类似的，我们可以得到 g(3)=-\dfrac{f(3)g(1)}{f(1)},g(4)=-\dfrac{f(4)g(1)}{f(1)}-\dfrac{f(2)g(2)}{f(1)} 等。注意 4 除了因子 1,4 还有因子 2，不能落下。

由此，我们可以归纳出 g 的递推公式。

g(n)= \begin{cases} \dfrac{1}{f(n)} & n=1\\ \\ -\dfrac{\displaystyle\sum_{d\mid n,d>1}f(d)g\left(\dfrac{n}{d}\right)}{f(1)} & n\neq1(\text{otherwise}) \end{cases}

同样考虑分类讨论。

不妨进行归纳假设： 对所有满足 \gcd(m,n)=1，且 m\le a,n\le b 的正整数 m,n，都有 g(nm)=g(n)g(m)。

设 \gcd(a,b)=1。由互质整数因数唯一分解的性质： 若 d\mid ab，则存在唯一分解 d=d_1d_2，满足 d_1\mid a,d_2\mid b,\gcd(d_1,d_2)=1。

求和条件为 d\mid ab,d>1，将满足条件的 (d_1,d_2) 划分为三类互不相交的情形：

对于求和进行拆分：

\sum_{d\mid ab,d>1}=\sum_{\substack{d_1\mid a,d_1>1\\d_2\mid b,d_2>1}}+\sum_{\substack{d_1=1\\d_2\mid b,d_2>1}}+\sum_{\substack{d_1\mid a,d_1>1\\d_2=1}}

代入原式：

g(ab)=-\dfrac{\displaystyle\sum_{d\mid ab,d>1} f(d)g\left(\dfrac{ab}{d}\right)}{f(1)}

将 d=d_1d_2 代入每一项：

\begin{align*} g(ab)=&-\dfrac{1}{f(1)}\Bigg[ \sum_{\substack{d_1\mid a,d_1>1\\d_2\mid b,d_2>1}} f(d_1d_2)g\left(\dfrac{ab}{d_1d_2}\right)\\ &+\sum_{d_2\mid b,d_2>1}f(d_2)g\left(\dfrac{ab}{d_2}\right) +\sum_{d_1\mid a,d_1>1}f(d_1)g\left(\dfrac{ab}{d_1}\right)\Bigg] \end{align*}

结合数论积性函数常用条件 f(1)=1，去掉系数 \dfrac{1}{f(1)}，展开得到：

\begin{align*} g(ab)=&-\sum_{\substack{d_1\mid a,d_1>1}}\sum_{\substack{d_2\mid b,d_2>1}} f(d_1d_2)g\left(\frac{ab}{d_1d_2}\right)\\ &-\sum_{\substack{d_2\mid b,d_2>1}} f(d_2)g\left(\frac{ab}{d_2}\right) -\sum_{\substack{d_1\mid a,d_1>1}} f(d_1)g\left(\frac{ab}{d_1}\right) \end{align*}

上下行分开来看。

上：

\begin{align*} &\quad -\sum_{d_1\mid a,d_1>1}\sum_{d_2\mid b,d_2>1} f(d_1d_2)g\left(\dfrac{ab}{d_1d_2}\right)\\ &=-\sum_{d_1\mid a,d_1>1}\sum_{d_2\mid b,d_2>1}f(d_1)f(d_2)g\left(\dfrac{a}{d_1}\right)g\left(\dfrac{b}{d_2}\right)\\ &=-\sum_{d_1\mid a,d_1>1}f(d_1)g\left(\dfrac{a}{d_1}\right)\sum_{d_2\mid b,d_2>1}f(d_2)g\left(\dfrac{b}{d_2}\right)\\ &=-(-f(1)g(a))(-f(1)g(b))\\ &=-g(a)g(b) \end{align*}

倒数第二步是递推公式的简单转化。中间的 g 为积性函数是开头假设的，有一定范围。我们要从小范围推大范围，最后推向普遍（数学归纳法）。

同理，下：

\begin{align*} &\quad -\sum_{\substack{d_2\mid b,d_2>1}} f(d_2)g\left(\frac{ab}{d_2}\right) -\sum_{\substack{d_1\mid a,d_1>1}} f(d_1)g\left(\frac{ab}{d_1}\right)\\ &=-\sum_{d_2\mid b,d_2>1}f(d_2)g\left(\dfrac{b}{d_2}\right)g(a)-\sum_{d_1\mid a,d_1>1}f(d_1)g\left(\dfrac{a}{d-1}\right)g(b)\\ &=f(1)g(b)g(a)+f(1)g(a)g(b)\\ &=2g(a)g(b) \end{align*}

两者相加得到原式 =-g(a)g(b)+2g(a)g(b)=g(a)g(b)。

也就是 g(ab)=g(a)g(b)，满足积性函数性质。

故我们通过数学归纳法证明了狄利克雷逆元为积性函数。
::::
## 如何求狄利克雷卷积？
### 朴素的 O(n\log n)
对于等式 h(n)=\displaystyle\sum_{xy=n}f(x)g(y)，可以直接枚举 x 和 y，将 f(x)g(y) 加到 h(xy) 上。假设要求所有 1\le i\le n 的 h(i) 的值，那么时间复杂度为 O\left(\displaystyle\sum_{i=1}^n\dfrac{n}{i}\right)=O(n\log n)，调和级数。
### 更多方案
适用于 f,g,h 中有积性函数时。具体可见 OI-wiki。
# 莫比乌斯反演
## 莫比乌斯反演是干什么的？
假设我们要求一个函数 f(n) 的值，但是很困难。考虑构造其容易求出的因数或倍数函数 g(n)，然后通过莫比乌斯反演反推出 f(n)。
## 什么是莫比乌斯函数？
令分解质因数后 n=p_1^{c_1}p_2^{c_2}\cdots p_x^{c_x}。莫比乌斯函数 \mu 定义为：
$$
\mu(n)=
\begin{cases}
1 & n=1\
0 & \exists c_i>1(1\le i\le x)\
(-1)^x & \forall c_i=1(1\le i\le x)
\end{cases}
$$
易得莫比乌斯函数为积性函数。
## 莫比乌斯函数有哪些性质？
这里就写比较重要的一个，也是莫比乌斯反演的基础。
::::success[性质]
> \displaystyle\sum_{d\mid n}\mu(d)=[n=1]。
> 也就是说 n=1 时为 1，否则为 0。
:::info[证明]
证明也很简单。

首先分解质因数得 n=\displaystyle\prod_{i=1}^kp_i^{c_i}，再令 m=\displaystyle\prod_{i=1}^kp_i。显然根据定义有 \displaystyle\sum_{d\mid n}\mu(d)=\sum_{d\mid m}\mu(d)=\displaystyle\sum_{i=0}^k{k\choose i}(-1)^i。因为那些 p_i 的倍数有显然为 0 没有贡献。

然后考虑二项式定理，得到 \displaystyle\sum_{i=0}^k{k\choose i}(-1)^i=(1+(-1))^k=[k=0]=[n=1]。注意，此时我们规定 0^0=1，但是这显然只适用在特殊情境中。

证完了。
然后这个性质有一个应用。
> [i\perp j]=[\gcd(i,j)=1]=\displaystyle\sum_{d\mid\gcd(i,j)}\mu(d)=\displaystyle\sum_d[d\mid i][d\mid j]\mu(d)。
> ——摘自 OI_wiki。
::::
## 如何求莫比乌斯函数？
### 仅求一个 \mu(n)
对 n 质因数分解，由定义可以做到 O(\sqrt{n})。
::::success[代码]
```cpp
int mu(int n){
int ans=1;
for(int i=2;i*i<=n;i++){
if(n%i==0){
n/=i;
if(n%i==0) return 0;//含多个相同质因数
ans=-ans;
}
}
if(n>1) ans=-ans;
return ans;
}
```
::::
### 求出 1\le i\le n 的所有 \mu(i)
由莫比乌斯函数为积性函数可以结合线性筛做到 O(n)。
::::success[代码]
```cpp
void mu(int n){
mu[1]=1,vis[0]=vis[1]=1;
for(int i=2;i<=n;i++){
if(!p[i]) p[++cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt&&p[j]*i<=n;j++){
vis[p[j]*i]=1;
if(i%p[j]==0){mu[p[j]*i]=0;break;}
else mu[p[j]*i]=-mu[i];
}
}
}
```
::::
## 何为莫比乌斯反演？
由名称我们可以知道与莫比乌斯函数和反演有关 （废话）。

莫比乌斯反演：假设现在有两个数论函数 f,g，那么如果 f(n)=\displaystyle\sum_{d\mid n}g(d)，则 g(n)=\displaystyle\sum_{d\mid n}f(d)\mu\left(\dfrac{n}{d}\right)。反过来同样成立。 ::::info[证明 1] 不妨直接代入。

\begin{align*} \displaystyle\sum_{d\mid n}f(d)\mu\left(\dfrac{n}{d}\right)&=\displaystyle\sum_{d\mid n}\mu\left(\dfrac{n}{d}\right)\sum_{k\mid d}g(k)\\ &=\sum_{k|n}g(k)\sum_d[k\mid d\mid n]\mu\left(\dfrac{n}{d}\right)\\ &=\sum_{k|n}g(k)\sum_{d\mid n}\left[\dfrac{n}{d}\mid\dfrac{n}{k}\right]\mu\left(\dfrac{n}{d}\right)\\ &=\sum_{k\mid n}g(k)\left[\dfrac{n}{k}=1\right]\\ &=g(n) \end{align*}

我们看看每一步是如何做到的：

我们考虑在 f=1\ast g 左右同时卷 \mu。得 f\ast \mu=(1\ast g)\ast \mu=(1\ast \mu)\ast g=\varepsilon\ast g=g。

此时左式用交换律就证完了。
哎我们是不是讲完了？

来讲两道例题吧。

例题详解

P3327 [SDOI2015] 约数个数和

设 d(x) 为 x 的约数个数，给定 n,m，求 \displaystyle\sum_{i=1}^n\displaystyle\sum_{j=1}^m d(ij)。

首先注意到 d(ij) 内部是两个都各自高达 50000 的数的乘积。有没有什么方法可以拆开呢？

有的，兄弟有的。扔出一个公式 d(ij)=\displaystyle\sum_{d_1\mid i}\displaystyle\sum_{d_2\mid j}[\gcd(d_1,d_2)=1]。

考虑一个简单的证明。假设现在有一个质数 p，我们设 i 中能分解出 a 个 p，j 中能分解出 b 个 p，即 p^a\mid i,p^{a+1}\nmid i,p^b\mid j,p^{b+1}\nmid j。那么 ij 中就有 a+b 个 p。方案选择数就是 a+b+1 种（即 0\sim a+b，与其他质因子结合）。考虑右边，我们需要证明方案选择数也为 a+b+1 种，这样每个 p 都满足条件，该等式显然成立。现在考虑为什么也是 a+b+1 种。

注意到右边有贡献当且仅当 \gcd(d_1,d_2)=1。这告诉我们，d_1,d_2 中至少有一个不包含质数 p，不然就不会互质啦！如果 d_1 不包含，那么 d_2 有 b+1 种选法，同理，如果 d_2 不包含，那么 d_1 有 a+1 种选法。再去掉都不包含的 1 种，就刚好是 a+b+1 种了。所以该等式成立。

代回原式得：

\sum_{i=1}^n\sum_{j=1}^m\sum_{d_1\mid i}\sum_{d_2\mid j}[\gcd(d_1,d_2)=1]

改变求和顺序，考虑先枚举因数 d_1,d_2，则 i,j 变为倍数：

\sum_{d_1=1}^n\sum_{d_2=1}^m\sum_{\substack{d_1\mid i\\1\le i\le n}}\sum_{\substack{d_2\mid j\\1\le j\le m}}[\gcd(d_1,d_2)=1]

注意到产生贡献条件 \gcd(d_1,d_2)=1 与内循环无关，所以内循环只提供数量，直接省略：

\sum_{d_1=1}^n\sum_{d_2=1}^m[\gcd(d_1,d_2)=1]\cdot \left\lfloor\dfrac{n}{d_1}\right\rfloor \cdot \left\lfloor\dfrac{m}{d_2}\right\rfloor

替换一下变量名称（由于 i 占位矮一点，下取整符号看上去有点小）：

\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1]\cdot\left\lfloor\dfrac{n}{i}\right\rfloor\cdot\left\lfloor\dfrac{m}{j}\right\rfloor

然后莫比乌斯反演，套路地设：

f(x)=\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=x]\cdot\left\lfloor\dfrac{n}{i}\right\rfloor\cdot\left\lfloor\dfrac{m}{j}\right\rfloor\\g(d)=\sum_{d\mid x}f(x)

我们要求 f(1)。

替换 f 得：

g(d)=\sum_{i=1}^n\sum_{j=1}^m[d\mid \gcd(i,j)]\cdot\left\lfloor\dfrac{n}{i}\right\rfloor\cdot\left\lfloor\dfrac{m}{j}\right\rfloor

直接令 d 为 \gcd(i,j) 的因数，也就是提出 d：

g(d)=\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}\left\lfloor\dfrac{n}{id}\right\rfloor\cdot\left\lfloor\dfrac{m}{jd}\right\rfloor=\sum_{i=1}^{\frac{n}{d}}\left\lfloor\dfrac{n}{id}\right\rfloor\sum_{j=1}^{\frac{m}{d}}\left\lfloor\dfrac{m}{jd}\right\rfloor

反演得到（这是倍数形式）：

f(n)=\sum_{n\mid d}\mu\left(\dfrac{d}{n}\right)g(d)

得到我们要求的 f(1)：

f(1)=\sum_{1\mid d}\mu\left(\dfrac{d}{1}\right)g(d)=\sum_{i=1}^n\mu(d)g(d)

只要算出 g(x) 就行。发现非常像整除分块啊。考虑预处理出 S_k=\displaystyle\sum_{i=1}^k\left\lfloor\dfrac{k}{i}\right\rfloor。那么 g(x)=S_{\frac{n}{x}}S_{\frac{m}{x}}，这是可以 O(N\sqrt{N}) 做的，其中 N 为 n 的最大值 50000。

而对 g(x) 再进行整除分块，预处理出 \mu 的前缀和就可以做到总时间复杂度为 O(N\sqrt{N}+T\sqrt{n}) 了。 ::::success[代码]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e4+5;
int t,n,m,tot,mu[N],p[N],S[N],pre[N];
bool vis[N];
void init(){
    mu[1]=1,vis[0]=vis[1]=1;
    for(int i=2;i<=N-5;i++){
        if(!vis[i]) p[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot&&p[j]*i<=N-5;j++){
            vis[i*p[j]]=1;
            if(i%p[j]==0){mu[p[j]*i]=0;break;}
            else mu[p[j]*i]=-mu[i];
        }
    }
    for(int i=1;i<=N-5;i++) pre[i]=pre[i-1]+mu[i];
    for(int i=1;i<=N-5;i++){
        int j=1;
        while(j<=i){
            int k=i/(i/j);
            S[i]+=i/k*(k-j+1);
            j=k+1;
        }
    }
}
signed main(){
    scanf("%lld",&t);init();
    while(t--){
        scanf("%lld%lld",&n,&m);
        if(n>m) swap(n,m);
        int ans=0,i=1;
        while(i<=n){
            int j=min(n/(n/i),m/(m/i));
            ans+=(pre[j]-pre[i-1])*S[n/i]*S[m/i];
            i=j+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

::::

P2257 YY的GCD

给定 N,M，求 1\le x\le N,1\le y\le M 且 \gcd(x,y) 为质数的 (x,y) 有多少对。

转化题意变成要求 \displaystyle\sum_{i=1}^N\sum_{j=1}^M[\gcd(i,j)=p]，其中 p 为质数。发现和之前的一些式子非常相似，可以考虑莫比乌斯反演。

以下 N,M 用小写字母表示，即 n,m。

套路地设：

f(x)=\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=x]\\g(d)=\sum_{d\mid x}f(x)=\left\lfloor\dfrac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor

反演得到：

f(d)=\sum_{d\mid x}\mu\left(\dfrac{x}{d}\right)g(x)

那么答案就是：

\begin{align*} \text{ans}&=\sum_{p\in\text{prime}}\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=p]\\ &=\sum_{p\in\text{prime}}f(p)\\ &=\sum_{p\in\text{prime}}\sum_{p\mid x}\mu\left(\dfrac{x}{p}\right)g(x)\\ &=\sum_{p\in\text{prime}}\sum_{p\mid x}\mu\left(\dfrac{x}{p}\right)\left\lfloor\dfrac{n}{x}\right\rfloor\left\lfloor\dfrac{m}{x}\right\rfloor\\ &=\sum_{x=1}^{\min(n,m)}\left\lfloor\dfrac{n}{x}\right\rfloor\left\lfloor\dfrac{m}{x}\right\rfloor\left(\sum_{p\in\text{prime},p\mid x}\mu\left(\dfrac{x}{p}\right)\right) \end{align*}

然后就和上一题的整除分块一样了。直接预处理出后面那一坨的前缀和即可。不妨令 g_i=\displaystyle\sum_{p\in\text{prime},p\mid i}\mu\left(\dfrac{i}{p}\right)，可以考虑枚举每一个质数的倍数。

时间复杂度 O(N\log\log N+T\sqrt{n})。其中 N 为 10^7。至于这个 \log\log 怎么来的，\displaystyle\sum_{p\in\text{prime},p\le N}\frac{1}{p} \approx \log\log N。类似埃氏筛，证明请自行了解，因为这与本专题无直接关联。 ::::success[代码]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7+5;
int t,n,m,p[N],tot,mu[N],pre[N],g[N];
bool vis[N];
void init(){
    mu[1]=1,vis[0]=vis[1]=1;
    for(int i=2;i<=N-5;i++){
        if(!vis[i]) p[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot&&p[j]*i<=N-5;j++){
            vis[i*p[j]]=1;
            if(i%p[j]==0){mu[p[j]*i]=0;break;}
            else mu[p[j]*i]=-mu[i];
        }
    }
    for(int j=1;j<=tot;j++)
        for(int i=1;p[j]*i<=N-5;i++)
            g[p[j]*i]+=mu[i];
    for(int i=1;i<=N-5;i++) pre[i]=pre[i-1]+g[i];
}
signed main(){
    init();
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&m);
        if(n>m) swap(n,m);
        int ans=0,i=1;
        while(i<=n){
            int j=min(n/(n/i),m/(m/i));
            ans+=(pre[j]-pre[i-1])*(n/i)*(m/i);
            i=j+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

::::

习题

学完知识点肯定要复习啊。不要偷懒呦！

按照笔者的主观难度顺序排序。题目仅供参考。