大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
狄利克雷卷积 以及 杜教筛学习笔记
突然对交换求和符号有了新的理解了，用矩阵转置的思路就很好理解，外层循环相当于枚举行，内层枚举列，交换次序就是先枚举列，再枚举行
方阵
正常的就是 ∑ i = 1 n ∑ j = 1 n f ( i , j ) = ∑ j = 1 n ∑ i = 1 n f ( i , j ) \sum_{i=1}^n \sum_{j=1}^nf(i,j)=\sum_{j=1}^n \sum_{i=1}^nf(i,j) i=1∑nj=1∑nf(i,j)=j=1∑ni=1∑nf(i,j)
再写成习惯的i在外面,j在里面,相当于换哈元 = ∑ i = 1 n ∑ j = 1 n f ( j , i ) =\sum_{i=1}^n \sum_{j=1}^nf(j,i) =∑i=1n∑j=1nf(j,i)
相当于原来元素 f ( i , j ) f(i,j) f(i,j)的位置变成了 f ( j , i ) f(j,i) f(j,i)
下三角
∑ i = 1 n ∑ j = i n f ( i , j ) = ∑ j = 1 n ∑ j = i n f ( i , j ) \sum_{i=1}^n \sum_{j=i}^nf(i,j)=\sum_{j=1}^n \sum_{j=i}^nf(i,j) i=1∑nj=i∑nf(i,j)=j=1∑nj=i∑nf(i,j)
这个就是常见的去重的时候的枚举，行数不超过列数
同样想成想成先枚举列再枚举行
换哈元 = ∑ i = 1 n ∑ j = i n f ( j , i ) =\sum_{i=1}^n \sum_{j=i}^nf(j,i) =∑i=1n∑j=inf(j,i)和上面差不多
约数倍数
如果上面的很容易理解来试一哈这种约数倍数的哇，这个就是像杜教筛的题里面要用到的
∑ i = 1 n ∑ j ∣ i n f ( i , j ) = ? \sum_{i=1}^n\sum_{j|i}^nf(i,j)=? i=1∑nj∣i∑nf(i,j)=?
其中 i ∣ j i|j i∣j是表示 i 是 j i是j i是j的约数，比如当 j = 6 j=6 j=6的时候， i i i就要枚举 1 , 2 , 3 , 6 1,2,3,6 1,2,3,6
这个也要从矩阵转置的角度来看，长得也和下三角差不多，只不过没有完全填充
交换次序就是先枚举列再枚举行，变成
∑ j = 1 n ∑ j ∣ i n f ( i , j ) \sum_{j=1}^n\sum_{j|i}^nf(i,j) j=1∑nj∣i∑nf(i,j)
这里内层求和还是 j 是 i 的 约 数 , i 是 j 的 倍 数 , 也 就 是 i = k j , k = 1 , 2 , 3… j是i的约数,i是j的倍数,也就是i=kj,k=1,2,3… j是i的约数,i是j的倍数,也就是i=kj,k=1,2,3...
所以在内层求和我们就阔以直接除以 j j j，这样 i i i就阔以从 1 1 1开始枚举了
变成 ∑ j = 1 n ∑ i = 1 [ n j ] f ( i j , j ) , 因 为 要 保 持 不 变 , 里 面 就 要 变 成 f ( i ⋅ j , j ) \sum_{j=1}^n\sum_{i=1}^{[\frac{n}{j}]}f(ij,j),因为要保持不变,里面就要变成f(i\cdot j,j) j=1∑ni=1∑[jn]f(ij,j),因为要保持不变,里面就要变成f(i⋅j,j)
然后再换一哈字母变成熟悉的样子，就变成了：
∑ i = 1 n ∑ j = 1 [ n i ] f ( j i , i ) \sum_{i=1}^n\sum_{j=1}^{[\frac{n}{i}]}f(ji,i) i=1∑nj=1∑[in]f(ji,i)
最 终 的 等 式 就 是 : ∑ i = 1 n ∑ j ∣ i n f ( i , j ) = ∑ i = 1 n ∑ j = 1 [ n i ] f ( j i , i ) 最终的等式就是:\sum_{i=1}^n\sum_{j|i}^nf(i,j)=\sum_{i=1}^n\sum_{j=1}^{[\frac{n}{i}]}f(ji,i) 最终的等式就是:i=1∑nj∣i∑nf(i,j)=i=1∑nj=1∑[in]f(ji,i)
那我们就用杜教筛的式子来套一哈喃，看对不对，原等式是这样的：
∑ i = 1 n ∑ d ∣ i n g ( d ) ⋅ f ( i d ) = ∑ i = 1 n g ( i ) ⋅ ∑ j = 1 n i f ( j ) \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) i=1∑nd∣i∑ng(d)⋅f(di)=i=1∑ng(i)⋅j=1∑inf(j)
这里把 j j j换成 d d d更有约数这个含义一些，不影响，其中的
∑ i = 1 n ∑ d ∣ i n g ( d ) ⋅ f ( i d ) = ∑ i = 1 n ∑ d = 1 [ n i ] g ( d ) ⋅ f ( d i d ) = ∑ i = 1 n ∑ d = 1 [ n i ] g ( d ) ⋅ f ( i ) , 然 后 g ( d ) 阔 以 提 出 去 = ∑ i = 1 n g ( i ) ⋅ ∑ j = 1 n i f ( j ) \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) i=1∑nd∣i∑ng(d)⋅f(di)=i=1∑nd=1∑[in]g(d)⋅f(ddi)=i=1∑nd=1∑[in]g(d)⋅f(i),然后g(d)阔以提出去=i=1∑ng(i)⋅j=1∑inf(j)
嗯(✪ω✪)一模一样٩(๑>◡<๑)۶
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/182682.html原文链接：https://javaforall.net
