反演&&杜教筛

63 阅读 0 评论 42 点赞

我是靠谱客的博主爱笑香水，最近开发中收集的这篇文章主要介绍反演&&杜教筛，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

大力鸣谢曲神的blog

反演

曾经naive的博主写的反演讲解
反演中常见公式

杜教筛

从未见过如此厚颜无耻之博主，说好了要讲反演nei，为什么只给两个链接？？？
好吧，我承认这篇文主要是想说说自己对杜教筛的崭新认识，所以下面才是正文。。。

学杜教筛之前，一定要做一件事：%糖教

简介

杜教筛是干什么的内？求解积性函数前缀和的有力工具
划重点：积性函数，前缀和

积性函数

常见积性函数
- 除数函数 σk(n)=∑d|ndk σ k ( n ) = ∑ d | n d k ，表示 n n 的约数的 $k$ 次幂和，注意 σk(n) σ k ( n ) 与 σk(n) σ k ( n ) 是不同的
- 约数个数函数 τ(n)=σ0(n)=∑d|n1 τ ( n ) = σ 0 ( n ) = ∑ d | n 1 ，表示 n n 的约数个数，一般也写为 $d (n)$
- 约数和函数 σ(n)=σ1(n)=∑d|nd σ ( n ) = σ 1 ( n ) = ∑ d | n d ，表示 n n 的约数之和
- 欧拉函数 $φ (n) = \sum_{i = 1}^{n} [(n, i) = 1]$ ，表示不大于 n n 且与 $n$ 互质的正整数个数
  另外 ∑ni=1[(n,i)=1]⋅i=n⋅φ(n)+[n=1]2 ∑ i = 1 n [ ( n , i ) = 1 ] ⋅ i = n ⋅ φ ( n ) + [ n = 1 ] 2 （互质数之和）
- 莫比乌斯函数 μ(n) μ ( n ) ，在狄利克雷卷积的乘法中与恒等函数互为逆元， μ(1)=1 μ ( 1 ) = 1 ，对于无平方因子数 n=∏ti=1pi n = ∏ i = 1 t p i 有 μ(n)=(−1)t μ ( n ) = ( − 1 ) t ，对于有平方因子数 n n 有 $μ (n) = 0$
- 元函数 e(n)=[n=1] e ( n ) = [ n = 1 ] ，狄利克雷卷积的乘法单位元，完全积性
- 恒等函数 I(n)=1 I ( n ) = 1 ，完全积性
- 单位函数 id(n)=n i d ( n ) = n ，完全积性
- 幂函数 idk(n)=nk i d k ( n ) = n k ，完全积性
关于莫比乌斯函数和欧拉函数的经典公式
- [n=1]=∑d|nμ(d) [ n = 1 ] = ∑ d | n μ ( d ) ，将 μ(d) μ ( d ) 看作是容斥的系数即可证明
- n=∑d|nφ(d) n = ∑ d | n φ ( d ) ，将 in(1≤i≤n) i n ( 1 ≤ i ≤ n ) 化为最简分数统计个数即可证明
- μ∗I=e μ ∗ I = e
- ϕ∗I=id(n) ϕ ∗ I = i d ( n )
若 f(n) f ( n ) 为积性函数，则对于正整数 n=∏ti=1pkii n = ∏ i = 1 t p i k i 有 f(n)=∏ti=1f(pkii) f ( n ) = ∏ i = 1 t f ( p i k i )
若 f(n) f ( n ) 为完全积性函数，则对于正整数 n=∏ti=1pkii n = ∏ i = 1 t p i k i 有 f(n)=∏ti=1f(pi)ki f ( n ) = ∏ i = 1 t f ( p i ) k i

综述

有数论函数 f(n) f ( n ) ，求 S(n)=∑ni=1f(i) S ( n ) = ∑ i = 1 n f ( i )
那么对于任意数论函数 g(n) g ( n ) ，满足 ∑ni=1(f∗g)(i)=∑ni=1g(i)S(ni) ∑ i = 1 n ( f ∗ g ) ( i ) = ∑ i = 1 n g ( i ) S ( n i )

证明

\sum i = 1 n (f * g) (i) = \sum i = 1 n \sum d | i f (i) g (i d) \sum i = 1 n ( f * g ) ( i ) = \sum i = 1 n \sum d | i f ( i ) g ( i d )

考虑枚举 j=id j = i d ，那么就是

\sum j = 1 n g (j) \sum p f (p) \sum j = 1 n g ( j ) \sum p f ( p )

考虑如何枚举 p p ？
也就是我们固定了 $\frac{i}{d}$ ，再考虑所有对ta造成贡献的 d d
这样我们就可以考虑枚举一层 $d$ （换成 p p ），得到 $i = p j$
我们可以想到，只要这里的 i<=n i <= n ，这个 p p 就是合法的
这样就限制了 $p$ 枚举的上界： nj n j ，则有：

\sum i = 1 n \sum d | i f (d) g (i d) \sum i = 1 n \sum d | i f ( d ) g ( i d )

= \sum j = 1 n g (j) \sum p = 1 n j f (p) = \sum j = 1 n g ( j ) \sum p = 1 n j f ( p )

= \sum i = 1 n g (i) \sum d = 1 n i f (d) = \sum i = 1 n g ( i ) \sum d = 1 n i f ( d )

= \sum i = 1 n g (i) S (n i) = \sum i = 1 n g ( i ) S ( n i )

这样得到：

g (1) S (n) = \sum i = 1 n (f * g) (i) - \sum i = 2 n g (i) S (n i) g ( 1 ) S ( n ) = \sum i = 1 n ( f * g ) ( i ) - \sum i = 2 n g ( i ) S ( n i )

一般的，我们找的 g(n) g ( n ) 是个积性函数或者常函数， g(1) g ( 1 ) 一般为1，而且意味着 f∗g f ∗ g 和 g g 是很好求和的函数

这样我们只需要对 $\sum_{i = 2}^{n} g (i) s (\frac{n}{i})$ 分块即可

总的来说：

如果能通过狄利克雷卷积构造一个更好计算前缀和的函数，且用于卷积的另一个函数也易计算，则可以简化计算过程

这样我们在遇到积性函数的前缀和的时候，直接套上式子即可（即使忘记了我们还是可以重新通过证明倒出来）

经典例题

1. 杜教筛 ϕ ϕ 之和

计算 ∑ni=1ϕ(i) ∑ i = 1 n ϕ ( i )
ϕ∗I=id ϕ ∗ I = i d ，简单的，我们卷上一个 I I （常函数）

S (n) = \sum_{i = 1}^{n} (ϕ * I) (i) - \sum_{i = 2}^{n} S (\frac{n}{i})

= \sum i = 1 n i - \sum i = 2 n S (n i) = n ( n + 1 ) 2 - \sum i = 2 n S (n i) = \sum i = 1 n i - \sum i = 2 n S ( n i ) = n ( n + 1 ) 2 - \sum i = 2 n S ( n i )

2. 杜教筛 μ μ 之和

计算 ∑ni=1μ(i) ∑ i = 1 n μ ( i )
μ∗I=e μ ∗ I = e ，我们还是卷上一个 I I

S (n) = \sum_{i = 1}^{n} (μ * I) (i) - \sum_{i = 2}^{n} S (\frac{n}{i}) = 1 - \sum_{i = 2}^{n} S (\frac{n}{i})

3 . 杜教筛 d d 之和

求 $\sum_{i = 1}^{n} d (i)$
d∗μ=1 d ∗ μ = 1 ，我们卷上 μ μ

S (n) = \sum i = 1 n (d * μ) (i) - \sum i = 2 n μ (i) S (n i) = n - \sum i = 2 n μ (i) S (n i) S ( n ) = \sum i = 1 n ( d * μ ) ( i ) - \sum i = 2 n μ ( i ) S ( n i ) = n - \sum i = 2 n μ ( i ) S ( n i )

4 . 杜教筛 lcm l c m 之和

求 ∑ni=1∑mj=1lcm(i,j) ∑ i = 1 n ∑ j = 1 m l c m ( i , j )

\sum i = 1 n \sum j = 1 m l c m (i, j) \sum i = 1 n \sum j = 1 m l c m ( i , j )

= \sum i = 1 n \sum j = 1 m i j g c d ( i , j ) = \sum i = 1 n \sum j = 1 m i j g c d ( i , j )

= \sum d = 1 m i n (n, m) d \sum k = 1 m i n (n / d, m / d) μ (k) k 2 s u m (n k d) s u m (m k d) s u m (n) = n ( n + 1 ) 2 = \sum d = 1 m i n ( n , m ) d \sum k = 1 m i n ( n / d , m / d ) μ ( k ) k 2 s u m ( n k d ) s u m ( m k d ) s u m ( n ) = n ( n + 1 ) 2

= \sum T = 1 n n T m T \sum d | T d \cdot μ (T d) (T d) 2 = \sum T = 1 n n T m T \sum d | T d \cdot μ ( T d ) ( T d ) 2

显然预处理线筛一下 ∑d|Td⋅μ(Td)(Td)2 ∑ d | T d · μ ( T d ) ( T d ) 2 即可

5. 杜教筛 gcd g c d 之和

求 ∑ni=1∑mj=1gcd(i,j) ∑ i = 1 n ∑ j = 1 m g c d ( i , j )

\sum i = 1 n \sum j = 1 m \sum d | g c d (i, j) ϕ (d) \sum i = 1 n \sum j = 1 m \sum d | g c d ( i , j ) ϕ ( d )

= \sum i = 1 n \sum j = 1 m \sum d = 1 m i n (n, m) \sum d | i \sum d | j ϕ (d) = \sum i = 1 n \sum j = 1 m \sum d = 1 m i n ( n , m ) \sum d | i \sum d | j ϕ ( d )

= \sum d = 1 m i n (n, m) ϕ (d) \sum i = 1 n \sum j = 1 m \sum d | i \sum d | j 1 = \sum d = 1 m i n ( n , m ) ϕ ( d ) \sum i = 1 n \sum j = 1 m \sum d | i \sum d | j 1

= \sum d = 1 m i n (n, m) ϕ (d) n d m d = \sum d = 1 m i n ( n , m ) ϕ ( d ) n d m d

杜教筛 ϕ(i) ϕ ( i ) 的前缀和即可

6 . 约数个数和
求 ∑ni=1∑mj=1d(i,j) ∑ i = 1 n ∑ j = 1 m d ( i , j )
d(i,j)=∑i|n∑j|m[gcd(i,j)=1] d ( i , j ) = ∑ i | n ∑ j | m [ g c d ( i , j ) = 1 ]

\sum i = 1 n \sum j = 1 m n i m j [g c d (i, j) = 1] \sum i = 1 n \sum j = 1 m n i m j [ g c d ( i , j ) = 1 ]

= \sum i = 1 n n i \sum j = 1 m m j \sum d = 1 \sum d | i \sum d | j μ (d) = \sum i = 1 n n i \sum j = 1 m m j \sum d = 1 \sum d | i \sum d | j μ ( d )

= \sum d = 1 μ (d) \sum i = 1 n n i \sum j = 1 m m j \sum d | i \sum d | j 1 = \sum d = 1 μ ( d ) \sum i = 1 n n i \sum j = 1 m m j \sum d | i \sum d | j 1

= \sum d = 1 μ (d) \sum p = 1 n / d n p d \sum q = 1 m / d m q d (i = p d, j = q d) = \sum d = 1 μ ( d ) \sum p = 1 n / d n p d \sum q = 1 m / d m q d ( i = p d , j = q d )

预处理 ∑n/dp=1npd ∑ p = 1 n / d n p d

7 . 求 ∑i=1μ(i)i2 ∑ i = 1 μ ( i ) i 2

[\sum i = 1 n μ (i) i 2] * \sum i = 1 i 2 [ \sum i = 1 n μ ( i ) i 2 ] * \sum i = 1 i 2

= \sum i = 1 n \sum d | i μ (d) d 2 (i d) 2 = \sum i = 1 n \sum d | i μ ( d ) d 2 ( i d ) 2

= \sum i = 1 n i 2 \sum d | i μ (d) = \sum i = 1 n i 2 \sum d | i μ ( d )

因为 ∑d|nμ(d)=[n=1] ∑ d | n μ ( d ) = [ n = 1 ]
所以上式

[\sum i = 1 n μ (i) i 2] * \sum i = 1 i 2 = 1 [ \sum i = 1 n μ ( i ) i 2 ] * \sum i = 1 i 2 = 1

设 S(n)=∑ni=1μ(i)i2 S ( n ) = ∑ i = 1 n μ ( i ) i 2

S (n) = 1 - \sum i = 2 n i 2 S (n i) S ( n ) = 1 - \sum i = 2 n i 2 S ( n i )

其中 ∑ni=1i2=n(n+1)(2n+1)6 ∑ i = 1 n i 2 = n ( n + 1 ) ( 2 n + 1 ) 6

最后

以上就是爱笑香水为你收集整理的反演&&杜教筛的全部内容，希望文章能够帮你解决反演&&杜教筛所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：数论
浏览次数：63 次浏览
发布日期：2024-09-05 23:50:01
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_7_o_14_f2_12__23_g1.html

反演&&杜教筛

概述

反演

杜教筛

简介

积性函数

综述

证明

经典例题

最后

评论列表共有 0 条评论

发表评论取消回复

反演&&杜教筛

概述

反演

杜教筛

简介

积性函数

综述

证明

经典例题

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

发表评论取消回复