莫比乌斯反演-让我们从基础开始

2018-07-14 11:48:39


提示:对于这种与gcd有关的式子别用莫比乌斯反演公式,会炸的

只需要记住:

$$[gcd(i,j)=1]=\sum_{d|gcd(i,j)}\mu(d)$$

证明?其实很简单。

$\mu$ 函数有个性质

$$\sum_{d|n}\mu(d)=[n=1]$$

将 $d$ 替换成 $gcd(i,j)$ 就是上面的那个暂且可以称作公式的式子了

例1

求 $$\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1]\ \ \ \ (n<m)$$

直接套公式啦

$$=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}\mu(d)$$

然后我们枚举 $d$ ,显然有 $d\in(1,n)\ \ \ (d|gcd(i,j))$

于是将 $d$ 提到前面去,则 $i,j$ 都是 $d$ 的倍数,化简一下,得

$$=\sum_{d=1}^{n}\mu(d)*\lfloor\frac{n}{d}\rfloor*\lfloor\frac{m}{d}\rfloor$$

注意到后面那一坨是可以 $O(\sqrt n)$ 分块做的

于是我们实现了 $O(n^2)$ 到 $O(\sqrt n)$ 的过渡

简单吧

例2

$$\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k]\ \ \ \ (n<m)$$

好像与上一题有点不一样

但我们可以转化成一样的

同时除以 $k$ ,得

$$=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(i,j)=1]$$

然后就一样了

例3

$$\sum_{i=1}^{n}\sum_{j=1}^{m}ij[gcd(i,j)=k]\ \ \ \ (n<m)$$

老方法,同时除以 $k$ ,只不过与上一题不同的是,我们需要考虑 $i,j$ 的贡献

$$=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}ij[gcd(i,j)=1]*k^2$$

有同学可能要问了

为什么最后要乘以一个 $k^2$ 啊?

因为在 $i,j$ 同时除以 $k$ 的同时,中间那个 $ij$ 的值就变了, $i,j$ 同时缩小到了原来的 $\frac{1}{k}$ ,所以最后要把缩小的乘回来,就是 $k^2$

让我们继续套路,将中间那个 $gcd(i,j)$ 用莫比乌斯替换掉

$$=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}ij\sum_{d|gcd(i,j)}\mu(d)*k^2$$

提出 $d$ ,同样,在最后乘以一个 $d^2$

$$=\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)*d^2\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{kd}\rfloor}ij*k^2$$

各归各家,各找各妈

$$=k^2*\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)*d^2\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}i\sum_{j=1}^{\lfloor\frac{m}{kd}\rfloor}j$$

我们发现,最后那两项,不就是 $\dots$ 等差数列吗?

时间复杂度 $O(n^2)\rightarrow O(\sqrt n)$

来一个强的

例4

求 $$\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)$$

首先,小学奥数告诉我们

$$lcm(i,j)=\frac{i*j}{gcd(i,j)}$$

可以看看我的另外一篇博客莫比乌斯反演-从莫比乌斯到欧拉,里面详细地介绍了一种奇妙的反演方法,大致思路是用 $\phi$ 函数替换 $\mu$ 函数。我暂且把它叫做欧拉反演

但是注意,如果 $gcd(i,j)$ 出现在分母这种不正常的位置,就不能用那个神奇的欧拉反演,而应该用常规方法。

先科普一下:积性函数,稍后会有用的

仍然是老套路,枚举 $gcd(i,j)$

$$=\sum_{d=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i*j}{d}*[gcd(i,j)=d]$$

同时除以 $d$

$$=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i*j*d*[gcd(i,j)=1]$$

$$=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i*j*d\sum_{k|gcd(i,j)}\mu(k)$$

枚举 $k$

$$=\sum_{d=1}^{n}d\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)*k^2\sum_{i=1}^{\lfloor\frac{n}{dk}\rfloor}i\sum_{j=1}^{\lfloor\frac{m}{dk}\rfloor}j$$

这时,这已经是一个 $O(n)$ 的做法,观察可以得到, $\lfloor\frac{n}{d}\rfloor$ 可以分一次块, $\lfloor\frac{n}{dk}\rfloor$ 可以再分一次块,总时间复杂度是 $O(\sqrt n*\sqrt n)=O(n)$

推到这里已经很牛逼了,但我们还有更好的方法,这个时间复杂度还能优化

后面那两坨等差数列很烦,我们把它换掉

设 $T=dk,f(x)=\sum_{i=1}^{x}i$ ,把原来那个式子换成

$$=\sum_{d=1}^{n}d\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)*k^2*f(\lfloor\frac{n}{T}\rfloor)*f(\lfloor\frac{m}{T}\rfloor)$$

看好了,下面的步骤很奇妙

用枚举 $gcd(i,j)$ 的方法,我们枚举 $T$

$$=\sum_{T=1}^{n}f(\lfloor\frac{n}{T}\rfloor)*f(\lfloor\frac{m}{T}\rfloor)\sum_{d|T}d*\mu(\frac{T}{d})*(\frac{T}{d})^2$$

$$=\sum_{T=1}^{n}f(\lfloor\frac{n}{T}\rfloor)*f(\lfloor\frac{m}{T}\rfloor)\sum_{d|T}d*\mu(d)*T$$

em $\dots$ 貌似没法用狄利克雷卷积

但别担心,我们观察最后这个式子

$$\sum_{d|T}d*\mu(d)*T$$

先不管 $T$

$$\sum_{d|T}d*\mu(d)$$

设 $$F(T)=\sum_{d|T}d*\mu(d)$$

我们考虑 $a\perp b$

$$F(a)=\sum_{d|a}d*\mu(d)$$

$$F(b)=\sum_{d|b}d*\mu(d)$$

显然 $a,b$ 对 $F(ab)$ 的贡献是没有交集的,而这时,在我们枚举 $d$ 时,它既可以是 $a$ 的约数,也可以是 $b$ 的约数,还能是 $ab$ 的约数。具体来说, $F(a)$ 的某一项乘 $F(b)$ 的某一项一定等于 $F(ab)$ 的某一项(一个 $a$ 的因子与一个 $b$ 的因子相乘一定是 $ab$ 的因子)

又因为 $a\perp b$ ,故有

$\mu(a$ 的某个因子 $k)*\mu(b$ 的某个因子 $j)=\mu(k*j)$

所以, $F$ 不就是一个积性函数吗?

常识告诉我们,积性函数是可以 $O(n)$ 筛的, $F$ 也一样

$$F(1)=1$$

如果 $a$ 是质数,则

$$F(a)=1-a$$
如果 $a\perp b$ ,则

$$F(a*b)=F(a)*F(b)$$

这三个公式易得出,我们考虑 $a\equiv 0\ (mod\ b)$ 且 $b$ 是质数的情况

则 $F(a*b)$ 比 $F(a)$ 多出的几项中, $d$ 分解后,项 $b$ 的次数一定大于 $1$

想一想,为什么

因为,如果 $b$ 这一项的次数小于等于 $1$ ,它就一定在 $F(a)$ 中被运算过了!( $a$ 一定有 $b$ 这个质因子)

别忘了,当某个数的某个质因子次数大于 $1$ ,它的 $\mu$ 值就是 $0$ 啊!

故此时

$$F(a*b)=F(a)$$

于是,我们推导出了 $F$ 函数的转移公式,代码表示如下(顺便处理一下前缀和)

void sieve() {
    F[1]=sum[1]=1;
    for (int i=2;i<=10000000;i++) {
        if (!flag[i]) prime[++cnt]=i,F[i]=1-i;
        for (int j=1;j<=cnt&&i*prime[j]<=10000000;j++) {
            flag[i*prime[j]]=1;
            if (i%prime[j]==0) {//不互质
                F[i*prime[j]]=F[i];
                break;
            }
            F[i*prime[j]]=F[i]*F[prime[j]];//互质
        }
        sum[i]=sum[i-1]+F[i]*i;
    }
}

回到公式

$$=\sum_{T=1}^{n}f(\lfloor\frac{n}{T}\rfloor)*f(\lfloor\frac{m}{T}\rfloor)\sum_{d|T}d*\mu(d)*T$$

仔细看代码,最后那个 $T$ 已经在前缀和中处理了

我们只需要分块求前面那两个 $f$ ,后面那一坨 $O(1)$ 处理(都筛出来了)

时间复杂度 $O(n)\rightarrow O(\sqrt n)$

当你想降一下时间复杂度时,枚举第二个分块中的某一项再进行处理可能是一个好选择。

例5

$$\sum_{i=1}^{n}\sum_{j=1}^{m}d(i*j)$$

其中, $d(i*j)$ 表示 $i*j$ 的约数个数

我们有一个公式

$$d(i*j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$$

很多人不知道这个公式是怎么推的,我来解释一下

其实,这里的 $[gcd(i,j)=1]$ 并不是为了去重,而是为了和左边的式子保持相等

我们考虑一个质数 $p$ , $i=i'*p^{k_1},j=j'*p^{k_2}$ ,注意这里 $k_1,k_2$ 可以为 $0$

考虑 $p$ 对 $d(i*j)$ 的贡献,显然,在 $d$ 的因子中, $p$ 的这一项可以为 $0$ ~ $k_1+k_2$ 共 $k_1+k_2+1$ 个

考虑等式右边,我们只看 $p$ 这一项。 $x=x'*p^{k_x},y=y'*p^{k_y}$

要满足 $gcd(x,y)=1$ ,那么就有 $gcd(p^{k_x},p^{k_y})=1$

要么 $k_x=0,k_y\in[0,k_2]$ ,共 $k_2+1$ 种

要么 $k_y=0,k_x\in[0,k_1]$ ,共 $k_1+1$ 种

减去重复判断的 $k_x=0,k_y=0$ 这种情况,最后答案 $k_1+k_2+1$ 种

与等式左边相同!

剩下的步骤都很水了,所以我把这留作练习,如果你认真阅读了以上所有内容,那么这个练习就可以轻松解决。

练习

练习1

上面说了

练习2

$$\prod_{i=1}^{n}\prod_{j=1}^{m}f[gcd(i,j)]\ \ \ (n,m\leq 10^6,T\leq 1000)$$

$f$ 是斐波那契数列

练习3

$$\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)^k\ \ \ (n,m\leq 5*10^6,T\leq 2000)$$

注:练习2、练习3中, $T$ 是数据组数

后记

感谢lyc大佬的指导,在他的帮助与耐心解答下,我才初识了懵逼钨丝反演莫比乌斯反演

只要掌握方法,能够耐心地进行推导,莫比乌斯系列的题目其实不难