数论题中（杜教筛）交换求和符号

全栈程序员-用户IM • 2022年10月12日下午8:00 • 未分类

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

文章目录

狄利克雷卷积以及杜教筛学习笔记

突然对交换求和符号有了新的理解了，用矩阵转置的思路就很好理解，外层循环相当于枚举行，内层枚举列，交换次序就是先枚举列，再枚举行

方阵

正常的就是 $\sum_{i=1}^n \sum_{j=1}^nf(i,j)=\sum_{j=1}^n \sum_{i=1}^nf(i,j)$

再写成习惯的i在外面,j在里面,相当于换哈元 $=\sum_{i=1}^n \sum_{j=1}^nf(j,i)$
相当于原来元素 $f (i, j)$ 的位置变成了 $f (j, i)$

下三角

$\sum_{i=1}^n \sum_{j=i}^nf(i,j)=\sum_{j=1}^n \sum_{j=i}^nf(i,j)$
这个就是常见的去重的时候的枚举，行数不超过列数
同样想成想成先枚举列再枚举行
换哈元 $=\sum_{i=1}^n \sum_{j=i}^nf(j,i)$ 和上面差不多

约数倍数

如果上面的很容易理解来试一哈这种约数倍数的哇，这个就是像杜教筛的题里面要用到的
$\sum_{i=1}^n\sum_{j|i}^nf(i,j)=?$
其中 $i ∣ j$ 是表示 $i 是 j$ 的约数，比如当 $j = 6$ 的时候， $i$ 就要枚举 $1, 2, 3, 6$

这个也要从矩阵转置的角度来看，长得也和下三角差不多，只不过没有完全填充

交换次序就是先枚举列再枚举行，变成
$\sum_{j=1}^n\sum_{j|i}^nf(i,j)$
这里内层求和还是 $j 是 i 的约数, i 是 j 的倍数, 也就是 i = k j, k = 1, 2, 3 . . .$
所以在内层求和我们就阔以直接除以 $j$ ，这样 $i$ 就阔以从 $1$ 开始枚举了
变成 $\sum_{j=1}^n\sum_{i=1}^{[\frac{n}{j}]}f(ij,j),因为要保持不变,里面就要变成f(i\cdot j,j)$
然后再换一哈字母变成熟悉的样子，就变成了：
$\sum_{i=1}^n\sum_{j=1}^{[\frac{n}{i}]}f(ji,i)$
$最终的等式就是:\sum_{i=1}^n\sum_{j|i}^nf(i,j)=\sum_{i=1}^n\sum_{j=1}^{[\frac{n}{i}]}f(ji,i)$
那我们就用杜教筛的式子来套一哈喃，看对不对，原等式是这样的：
$\sum_{i=1}^n\sum_{d|i}^ng(d)\cdot f(\frac{i}{d})=\sum_{i=1}^ng(i)\cdot \sum_{j=1}^{\frac{n}{i}}f(j)$
这里把 $j$ 换成 $d$ 更有约数这个含义一些，不影响，其中的
$\sum_{i=1}^n\sum_{d|i}^ng(d)\cdot f(\frac{i}{d})=\sum_{i=1}^n\sum_{d=1}^{[\frac{n}{i}]}g(d)\cdot f(\frac{di}{d})=\sum_{i=1}^n\sum_{d=1}^{[\frac{n}{i}]}g(d)\cdot f(i),然后g(d)阔以提出去=\sum_{i=1}^ng(i)\cdot \sum_{j=1}^{\frac{n}{i}}f(j)$
嗯(✪ω✪)一模一样٩(๑>◡<๑)۶