关于 gcd 卷积

IntoTheDusk · 2025-09-14 14:33:12 · 算法·理论

下面我们默认只考虑 1 \sim N 之内的正整数。这样子求和下标写起来可以更加简洁一些。

考虑这么一个问题：给定两个数论函数和一个正整数 n，求 h(n)=\sum\limits_{\gcd(i,j)=n}f(i)g(j)。

首先有一个东西叫做 Zeta 变换：f 的 Zeta 变换满足 \hat{f}(n)=\sum\limits_{n \mid k}f(k)。 然后我们注意到一个事实：

此时，若 n \mid k 和 \gcd(i,j)=k 同时成立，手模一下可知 n \mid i 且 n \mid j。于是，

欸，这个时候我们发现这个东西和我们所熟悉的卷积，和 FFT 和 NTT 啥的很像啊。我们可以把求 \hat{f},\hat{g} 视为一次变换，然后算出点积，最后试着逆变换回去。

于是，\forall 1 \le i \le N，我们可以先求出 \hat{f}(i) 和 \hat{g}(i)，这个如果你 f,g 的复杂度都是 O\left(1\right) 的话总的复杂度大致是 O\left(n \log n \right) 的。然后，类似 FFT 和 NTT，我们把 \hat{h}(i) 相应的值算出来。现在，我们只需要考虑怎么靠着我们求出来的 \hat{h} 在 1 \sim N 处的取值算出 h 在 1 \sim N 处的取值。

这里的话就有不少做法了。

比方说你可以莫反，显然 h(n)=\sum\limits_{d \mid n}\mu(\frac{n}{d})\hat{h}(d)，直接算即可。复杂度大概是 O\left(n \log n \right)。

当然还有不需要求 \mu 的做法。我们回忆一下，\hat{h}(n)=\sum\limits_{n \mid k}h(k)=\sum\limits_{d=1}^{\lfloor\frac{N}{n}\rfloor}h(nd)=h(n)+\sum\limits_{d=2}^{\lfloor\frac{N}{n}\rfloor}h(nd)。于是，h(n)=\hat{h}(n)-\sum\limits_{d=2}^{\lfloor\frac{N}{n}\rfloor}h(nd)。于是你就从远处开始往近处求值就行了。时间复杂度还是 O\left(n \log n \right)。

如果你问我 \rm{lcm} 的话其实也差不多，手推一下就行了。

这里贴一份实现。