反演水题 Collection

其实我不太想在这个博客扔刷题记录的……有点破坏博客排版

不过我还是决定单独开一篇来总结一下。这篇文章会随着我做题继续补充,以及代码会比推论稍微慢一点更新,都扔在 GitHub 上……

首先是上一篇乱七八糟的讲解 Möbius反演的文章,欢迎观赏: 不一样的反演魔术

先扔个比较常用的 Dirichlet 卷积结论:

因为 1=\displaystyle\sum_{d\mid n}[d=1] ,根据反演定理,直接有 [n=1]=\displaystyle\sum_{d\mid n}\mu(d)

因为 n=\displaystyle\sum_{d\mid n}\varphi(d) ,有 \varphi(n)=\displaystyle\sum_{d\mid n}d\mu\left(\frac nd\right) ,或用卷积表示: \varphi=\operatorname{id}*\mu

BZOJ 1101 [POI2007]Zap

给定 n,m,d ,问 \,\displaystyle\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]\,

同时将 i,j 除以 d 有: \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]=\sum_{i=1}^{\left\lfloor\large\frac nd\right\rfloor}\sum_{j=1}^{\left\lfloor\large\frac md\right\rfloor}[\gcd(i,j)=1]

根据 \delta=1*\mu ,将 [\gcd(i,j)=1] 化为 \,\displaystyle\sum_{r\mid\gcd(i,j)}\mu(r)\, ,原式化为: \sum_{i=1}^{\left\lfloor\large \frac nd\right\rfloor}\sum_{i=1}^{\left\lfloor\large \frac md\right\rfloor}\sum_{r\mid\gcd(i,j)}\mu(r)

\,\displaystyle\sum_{r\mid\gcd(i,j)}\, 提出 \,\displaystyle\sum_{i=1}^{\left\lfloor\large \frac nd\right\rfloor}\sum_{i=1}^{\left\lfloor\large \frac md\right\rfloor}\, 之外,原式化为: \sum_{r=1}^{\left\lfloor\min\left\{\large\frac nd,\frac md\right\}\right\rfloor}\mu(r)\sum_{i=1}^{\left\lfloor\large\frac n{rd}\right\rfloor}\sum_{j=1}^{\left\lfloor\large\frac n{rd}\right\rfloor}1

后半部分对 1 的累加可以直接化为 \,\displaystyle\left\lfloor\frac n{rd}\right\rfloor\left\lfloor\frac m{rd}\right\rfloor\, ,则最终得到公式: \begin{aligned}\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]=\sum_{r=1}^{\left\lfloor\min\left\{\large\frac nd,\frac md\right\}\right\rfloor}\mu(r)\left\lfloor\frac n{rd}\right\rfloor\left\lfloor\frac m{rd}\right\rfloor\end{aligned}

该式比较重要,可以作为很多题目题解的前置知识出现。

关于该式的求解,由于 \,\displaystyle\left\lfloor\frac n{rd}\right\rfloor\left\lfloor\frac m{rd}\right\rfloor\, 最多只有 \mathrm O\left(\sqrt{\max\{n,m\}}\right) 个,所以求得 \mu 函数的前缀和,枚举所有不同的二元组 \,\displaystyle\left(\left\lfloor\frac nk\right\rfloor,\left\lfloor\frac mk\right\rfloor\right)\, 即可,复杂度即为 \mathrm O\left(\sqrt{\max\{n,m\}}\right)

BZOJ 1101 代码

BZOJ 2045 双亲数

完全同上,双倍经验。

BZOJ 2045 代码

BZOJ 2190 [SDOI2008]仪仗队

给定 n ,问 \,\displaystyle\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=1]\, 。同上略。

BZOJ 2190 代码

BZOJ 2301 [HAOI2011]Problem b

给定 a,b,c,d,k ,问 \,\displaystyle\sum_{i=a}^b\sum_{j=c}^d[\gcd(i,j)=k]\,

和上题类似,设函数 F(n,m)=\displaystyle\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d] ,显然 F(n,m) 所组成的矩阵 \mathbf F_{n,m}=F(n,m) 相当于矩阵 \mathbf G_{n,m}=[\gcd(n,m)=1] 的二维前缀和,即 \mathbf F_{n,m}=\begin{cases}\mathbf G_{1,1}&\text{for }n=m=1\\\mathbf G_{1,m}+\mathbf F_{1,m-1}&\text{for }n=1\\\mathbf G_{n,1}+\mathbf F_{n-1,1}&\text{for }m=1\\\mathbf G_{n,m}+\mathbf F_{n-1,m}+\mathbf F_{n,m-1}-\mathbf F_{n-1,m-1}&\text{otherwise}\end{cases}

所以有 \,\displaystyle\sum_{i=a}^b\sum_{j=c}^d[\gcd(i,j)=k]=F(b,d)-F(a-1,d)-F(b,c-1)+F(a-1,c-1)\,

BZOJ 2301 代码

BZOJ 3930 [CQOI2015]选数

给定 N,K,L,H ,问 \,\displaystyle\underbrace{\sum_{k_1=L}^H\sum_{k_2=L}^H\sum_{k_3=L}^H\cdots\sum_{k_N=L}^H}_{N\text{ summations}}[\gcd(k_1,k_2,k_3,\cdots,k_N)=K]\pmod{10^9+7}\, 。别被一堆求和符号吓住了,本质还是一个把 \gcd 提出来的过程: \begin{aligned}&\underbrace{\sum_{k_1=L}^H\sum_{k_2=L}^H\sum_{k_3=L}^H\cdots\sum_{k_N=L}^H}_{N\text{ summations}}[\gcd(k_1,k_2,k_3,\cdots,k_N)=K]\\=&\underbrace{\sum_{k_1=\left\lfloor\large\frac{L-1}K\right\rfloor+1}^{\left\lfloor\large\frac HK\right\rfloor}\sum_{k_2=\left\lfloor\large\frac{L-1}K\right\rfloor+1}^{\left\lfloor\large\frac HK\right\rfloor}\sum_{k_3=\left\lfloor\large\frac{L-1}K\right\rfloor+1}^{\left\lfloor\large\frac HK\right\rfloor}\cdots\sum_{k_N=\left\lfloor\large\frac{L-1}K\right\rfloor+1}^{\left\lfloor\large\frac HK\right\rfloor}}_{N\text{ summations}}[\gcd(k_1,k_2,k_3,\cdots,k_N)=1]\\=&\underbrace{\sum_{k_1=\left\lfloor\large\frac{L-1}K\right\rfloor+1}^{\left\lfloor\large\frac HK\right\rfloor}\sum_{k_2=\left\lfloor\large\frac{L-1}K\right\rfloor+1}^{\left\lfloor\large\frac HK\right\rfloor}\sum_{k_3=\left\lfloor\large\frac{L-1}K\right\rfloor+1}^{\left\lfloor\large\frac HK\right\rfloor}\cdots\sum_{k_N=\left\lfloor\large\frac{L-1}K\right\rfloor+1}^{\left\lfloor\large\frac HK\right\rfloor}}_{N\text{ summations}}\sum_{d\mid\gcd(k_1,k_2,k_3,\cdots,k_N)}\mu(d)\\=&\sum_{d=1}^{\left\lfloor\large\frac HK\right\rfloor}\mu(d)\underbrace{\sum_{k_1=\left\lfloor\large\frac{L-1}{Kd}\right\rfloor+1}^{\left\lfloor\large\frac H{Kd}\right\rfloor}\sum_{k_2=\left\lfloor\large\frac{L-1}{Kd}\right\rfloor+1}^{\left\lfloor\large\frac H{Kd}\right\rfloor}\sum_{k_3=\left\lfloor\large\frac{L-1}{Kd}\right\rfloor+1}^{\left\lfloor\large\frac H{Kd}\right\rfloor}\cdots\sum_{k_N=\left\lfloor\large\frac{L-1}{Kd}\right\rfloor+1}^{\left\lfloor\large\frac H{Kd}\right\rfloor}}_{N\text{ summations}}1\\=&\sum_{d=1}^{\left\lfloor\large\frac HK\right\rfloor}\mu(d)\left(\left\lfloor\frac H{Kd}\right\rfloor-\left\lfloor\frac {L-1}{Kd}\right\rfloor\right)^N\end{aligned}

过程很艰辛,结果很简单,因为是两个分别整除后相减,所以还是按照 \,\displaystyle\left(\left\lfloor\frac H{Kd}\right\rfloor,\left\lfloor\frac{L-1}{Kd}\right\rfloor\right)\, 来分块枚举 d 。不过因为 \,\displaystyle\left\lfloor\frac HK\right\rfloor\, 最大有 10^9 ,所以需要杜教筛筛 \mu

BZOJ 3930 代码

BZOJ 2005 [Noi2010]能量采集

给定 n,m ,问 \,\displaystyle\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)\,

枚举最大公约数,提取出公约数设 \gcd(i,j)d 得到: \sum_{d=1}^{\min\{n,m\}}d\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]

后半部分的值我们在上一题中求过,直接带入得: \sum_{d=1}^{\min\{n,m\}}d\sum_{r=1}^{\left\lfloor\min\left\{\large\frac nd,\frac md\right\}\right\rfloor}\mu(r)\left\lfloor\frac n{rd}\right\rfloor\left\lfloor\frac m{rd}\right\rfloor

接下去设 k=rd ,枚举 kd ,则 r=\displaystyle\frac kd ,有: \sum_{k=1}^{\min\{n,m\}}\left\lfloor\frac nk\right\rfloor\left\lfloor\frac mk\right\rfloor\sum_{d|k}d\mu\left(\frac kd\right)

根据 \varphi=\mu*\operatorname{id} ,化为: \sum_{k=1}^{\min\{n,m\}}\varphi(k)\left\lfloor\frac nk\right\rfloor\left\lfloor\frac mk\right\rfloor

剩下的枚举求解与上题同理,复杂度 \mathrm O\left(\sqrt{\max\{n,m\}}\right)

这里有个技巧就是: \varphi*1=\operatorname{id} ,这就可以直接把 \gcd(i,j) 替换成 \,\displaystyle\sum_{k\mid\gcd(i,j)}\varphi(k)\, ,上式的推导会简单许多: \begin{aligned}&\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)\\=&\sum_{i=1}^n\sum_{j=1}^m\sum_{k\mid\gcd(i,j)}\varphi(k)\\=&\sum_{k=1}^{\min\{n,m\}}\varphi(k)\sum_{i=1}^{\left\lfloor\large\frac nk\right\rfloor}\sum_{j=1}^{\left\lfloor\large\frac mk\right\rfloor}1\end{aligned}

BZOJ 2005 代码

BZOJ 2693 jzptab

给定 n,m ,求 \,\displaystyle\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{\gcd(i,j)}\pmod{10^8+9}\,

类似地,枚举所有 \gcd(i,j)=d\sum_{d=1}^{\min\{n,m\}}\sum_{i=1}^n\sum_{j=1}^m\frac{ij}d[\gcd(i,j)=d]

i,j 同时除以 d 有: \sum_{d=1}^{\min\{n,m\}}\sum_{i=1}^{\left\lfloor\large\frac nd\right\rfloor}\sum_{j=1}^{\left\lfloor\large\frac md\right\rfloor}dij[\gcd(i,j)=1]

根据 \delta=1*\mu[\gcd(i,j)=1] 化为: \sum_{d=1}^{\min\{n,m\}}\sum_{i=1}^{\left\lfloor\large\frac nd\right\rfloor}\sum_{j=1}^{\left\lfloor\large\frac md\right\rfloor}dij\sum_{r\mid\gcd(i,j)}\mu(r)

\,\displaystyle\sum_{i=1}^{\left\lfloor\large\frac nd\right\rfloor}\sum_{j=1}^{\left\lfloor\large\frac md\right\rfloor}\, 右提出 \,\displaystyle\sum_{r\mid\gcd(i,j)}\sum_{d=1}^{\min\{n,m\}}\sum_{r=1}^{\left\lfloor\min\left\{\large\frac nd,\frac md\right\}\right\rfloor}d\mu(r)\sum_{i=1}^{\left\lfloor\large\frac n{rd}\right\rfloor}ri\sum_{j=1}^{\left\lfloor\large\frac m{rd}\right\rfloor}rj

由于式 \,\displaystyle\sum_{i=1}^{\left\lfloor\large\frac n{rd}\right\rfloor}ri\sum_{j=1}^{\left\lfloor\large\frac m{rd}\right\rfloor}rj\, 为两个等差数列求和,可以直接求得为: \frac{r^2}4\left\lfloor\frac n{rd}\right\rfloor\left\lfloor\frac m{rd}\right\rfloor\left(\left\lfloor\frac n{rd}\right\rfloor+1\right)\left(\left\lfloor\frac m{rd}\right\rfloor+1\right)

k=rd ,将原式改为枚举 k 和其因子 r ,则 d=\displaystyle\frac kr ,可得: \begin{aligned}&\sum_{k=1}^{\min\{n,m\}}\left(\sum_{i=1}^{\left\lfloor\large\frac nk\right\rfloor}i\sum_{j=1}^{\left\lfloor\large\frac mk\right\rfloor}j\right)\sum_{r\mid k}\frac krr^2\mu(r)\\=&\sum_{k=1}^{\min\{n,m\}}\left(\sum_{i=1}^{\left\lfloor\large\frac nk\right\rfloor}i\sum_{j=1}^{\left\lfloor\large\frac mk\right\rfloor}j\right)\sum_{r\mid k}kr\mu(r)\end{aligned}

和第一题类似地,我们通过对不同的 \,\displaystyle\left(\left\lfloor\frac nk\right\rfloor,\left\lfloor\frac mk\right\rfloor\right)\, 二元组进行迭代,用上面的等差数列求和公式 \mathrm O(1) 求出总计 \mathrm O\left(\sqrt{\max\{n,m\}}\right) 个区间内的 \,\displaystyle\sum_{i=1}^{\left\lfloor\large\frac nk\right\rfloor}i\sum_{j=1}^{\left\lfloor\large\frac mk\right\rfloor}j\, 值。

至于右侧的 \,\displaystyle\sum_{r\mid k}kr\mu(r)\, ,由于化简之前也是积性函数卷积的形式,它同样可以在线性筛中预处理。然后就和第一题一样的套路了。

BZOJ 2693 代码

LOJ 6229 这是一道简单的数学题

给定 n,m ,求 \,\displaystyle\sum_{i=1}^n\sum_{j=1}^i\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)}\,

如果求的是 \,\displaystyle\sum_{i=1}^n\sum_{j=1}^m\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)}\, 则和上一题几乎完全一样,由于 \,\displaystyle\operatorname{lcm}(i,j)=\frac{ij}{\gcd(i,j)}\, ,所以和上题的表达式就差了一个 \gcd(i,j) ,推导如下: \begin{aligned}&\sum_{i=1}^n\sum_{j=1}^m\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)}\\=&\sum_{d=1}^{\min\{n,m\}}\frac1{d^2}\sum_{i=1}^n\sum_{j=1}^mij[\gcd(i,j)=d]\\=&\sum_{d=1}^{\min\{n,m\}}\sum_{i=1}^{\left\lfloor\large\frac nd\right\rfloor}i\sum_{j=1}^{\left\lfloor\large\frac md\right\rfloor}j\sum_{r\mid\gcd(i,j)}\mu(r)\\=&\sum_{d=1}^{\min\{n,m\}}\sum_{r=1}^{\left\lfloor\min\{\large\frac nd,\frac md\}\right\rfloor}\mu(r)\sum_{i=1}^{\left\lfloor\large\frac n{rd}\right\rfloor}ri\sum_{j=1}^{\left\lfloor\large\frac m{rd}\right\rfloor}rj\\=&\sum_{k=1}^{\min\{n,m\}}\left(\sum_{i=1}^{\left\lfloor\large\frac nk\right\rfloor}i\sum_{j=1}^{\left\lfloor\large\frac mk\right\rfloor}j\right)\sum_{r\mid k}r^2\mu(r)\end{aligned}

至于 \,\displaystyle\sum_{i=1}^n\sum_{j=1}^i\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)}\, ,考虑到 \operatorname{lcm}(i,j)=\operatorname{lcm}(j,i),\gcd(i,j)=\gcd(j,i) ,所以和上式差了一倍加上 i=j 的情况,而当 i=j 时,显然 \operatorname{lcm}(i,j)=\gcd(i,j) ,因此为 1 。加入到原式即为: \sum_{i=1}^n\sum_{j=1}^i\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)}=\frac12\left(\sum_{i=1}^n\sum_{j=1}^n\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)}+n\right)

虽然该式理论上满足答案,不过本题由于 n 的范围太大,右侧的积性函数 \,\displaystyle\sum_{r\mid k}r^2\mu(r)\, 求和无法直接保存下来,因此需要用到高效积性函数前缀和算法(杜教筛,下面附上了杜教筛正确性的推导过程)。

首先定义几个函数: \begin{aligned}f(n)=&\sum_{k\mid n}k^2\mu(k)\\F(n)&=\sum_{k=1}^nf(k)\end{aligned}

杜教筛中,选取平方函数 \operatorname{sq} 为辅助函数,可观察得 f*\operatorname{sq}=1 。则有:\begin{aligned}&\sum_{d\mid k}d^2f\left(\frac kd\right)=1\\\implies&f(k)=1-\sum_{d\mid k\land d\neq k}\left(\frac kd\right)^2f(d)\\\implies&F(n)=\sum_{k=1}^nf(k)=\sum_{k=1}^n1-\sum_{k=1}^n\sum_{d\mid k\land d\neq k}\left(\frac kd\right)^2f(d)\\&\phantom{F(n)=\sum_{k=1}^nf(k)}=n-\sum_{r=2}^nr^2\sum_{d=1}^{\left\lfloor\large\frac nk\right\rfloor}f(d)&\triangleright\text{ Split }k\text{ into }r\times d.\\&\phantom{F(n)=\sum_{k=1}^nf(k)}=n-\sum_{r=2}^nr^2F\left(\left\lfloor\frac nr\right\rfloor\right)\end{aligned}

LOJ 6229 代码 (1)

不过针对本题,还有更简单的公式,不过利用该公式的话,除了杜教筛部分之外就和反演无关。利用公式 \,\displaystyle\sum_{k=1}^nk[\gcd(n,k)=1]=\frac12[n=1]+\frac12n\varphi(n) 推导出: \begin{aligned}&\sum_{d=1}^n\sum_{i=1}^{\left\lfloor\large\frac nd\right\rfloor}i\sum_{j=1}^ij[\gcd(i,j)=1]\\=&\frac n2+\frac12\sum_{d=1}^n\sum_{i=1}^{\left\lfloor\large\frac nd\right\rfloor}i^2\varphi(i)\\=&\frac n2+\frac12\sum_{i=1}^ni^2\varphi(i)\left\lfloor\frac ni\right\rfloor\end{aligned}

剩下的一样,按 \,\displaystyle\left\lfloor\frac nk\right\rfloor\, 分块处理 k^2\varphi(k) 即可,这是个积性函数,所以也可以(并且需要)用高效积性函数前缀和算法,同样选择辅助函数为平方函数 \operatorname{sq} ,容易得到卷积结果 (\varphi\operatorname{sq}*\operatorname{sq})(n)=\operatorname{sq}(n)(\varphi*1)(n)=\operatorname{cb}(n)=n^3 ,所以杜教筛就有: \begin{aligned}F(n)=&\sum_{k=1}^n(\varphi\operatorname{sq}*\operatorname{sq})(k)-\sum_{k=2}^n\operatorname{sq}(k)F\left(\left\lfloor\frac nk\right\rfloor\right)\\=&\sum_{k=1}^nk^3-\sum_{k=2}^nk^2F\left(\left\lfloor\frac nk\right\rfloor\right)\\=&\frac{n^2(n+1)^2}4-\sum_{k=2}^nk^2F\left(\left\lfloor\frac nk\right\rfloor\right)\end{aligned}

LOJ 6229 代码 (2)

Luogu P2257 YY的GCD

给定 n,m ,问 \,\displaystyle\sum_{i=1}^n\sum_{j=1}^m\operatorname{is-prime}(\gcd(i,j))\,

\begin{aligned}&\sum_{i=1}^n\sum_{j=1}^m\operatorname{is-prime}(\gcd(i,j))\\=&\sum_{d=1}^{\min\{n,m\}}\operatorname{is-prime}(d)\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]\\=&\sum_{d=1}^{\min\{n,m\}}\operatorname{is-prime}(d)\sum_{r=1}^{\left\lfloor\min\left\{\large\frac nd,\frac md\right\}\right\rfloor}\mu(r)\left\lfloor\frac n{rd}\right\rfloor\left\lfloor\frac m{rd}\right\rfloor\\=&\sum_{k=1}^{\min\{n,m\}}\sum_{d\mid k}\operatorname{is-prime}(d)\mu\left(\frac kd\right)\left\lfloor\frac nk\right\rfloor\left\lfloor\frac mk\right\rfloor\\\end{aligned}

已经可以了, 1k 之间的卷积可以 \mathrm O(k\log k) 处理,求个前缀和就又是模板题。

注意爆 int32_t 了,我测了最大的数据都没意识到有爆掉(毕竟答案有正有负)。

Luogu P2257 代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注