备课9-27
我不是柳橙汁
2019-09-27 19:12:02
### 目录
前置知识
莫比乌斯反演
杜教筛
min_25筛
## 前置知识
1.乘性函数
对于一个数论函数$f(n)$
若有两个互质的正整数$n,m$，使得
$$f(nm)=f(n)·f(m)$$
则这个函数为乘性函数
若有任意两个正整数$n,m$，使得
$$f(nm)=f(n)·f(m)$$
则这个函数为完全乘性函数
2.一些常用的乘性函数
$$I(n)=1$$
$$\epsilon(n)=[n=1]$$
$$id^k(n)=n^k$$
$$d(n)=\sum_{i=1}^n[n \space mod \space i=0]$$
$$\sigma_k(n)=\sum_{i=1}^n i^k[n \space mod \space i=0]$$
$$\varphi(n)=\sum_{i=1}^n [gcd(i,n)=1]$$
$$\mu(n)$$
3.狄利克雷卷积
对于两个积性函数$f,g$
我们定义他们的狄利克雷卷积是
$$h(n)=f(n)*g(n)=\sum_{d|n}f(d)g(\lfloor \frac{n}{d}\rfloor)$$
卷积满足交换律、结合律、分配律。
3.1一些常用的卷积
$$f*\epsilon=f$$
$$I*\mu=\epsilon$$
$$id*\mu=\varphi$$
$$\varphi*I=id$$
$$id*\mu=\varphi$$
## 莫比乌斯反演
1.定义
若对于$f,F$,有
$$F=f*I$$
则
$$f=F*\mu$$
2.证明
$$F*\mu=(f*I)*mu$$
$$=f*(I*\mu)$$
$$=f*\epsilon=f$$
3.某些常用套路
$$[n=1]=\sum_{d|n}\mu(d)$$
$$n=\sum_{d|n}\varphi(d)$$
例1 luogu P2257 YY的GCD
求
$$\sum_{k=1,k \space is \space prime}^n\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=d](n>=m)$$
解
$$=\sum_{k=1,k \space is \space prime}^n\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{i=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(i,j)=1]$$
$$=\sum_{k=1,k \space is \space prime}^n\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{i=1}^{\lfloor\frac{m}{k}\rfloor}\sum_{d|gcd(i,j)}\mu(d)$$
$$=\sum_{k=1,k \space is \space prime}^n \sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor$$
设$T=kd$,则
$$=\sum_{k=1,k \space is \space prime}^n \sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(\frac{T}{k})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor$$
$$=\sum_{T=1}^n\lfloor \frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{k|T,k\space is \space prime}\mu(\frac{T}{k})$$
前半部分数论分块，后半部分可以预处理，达到题目需要的时间复杂度
例2 luogu P3768 简单的数学题
求
$$\sum_{i=1}^{n}\sum_{j=1}^{m}ij·gcd(i,j)\space mod \space p$$
解
先不考虑$p$
$$\sum_{i=1}^{n}\sum_{j=1}^{n}ij·gcd(i,j)$$
枚举$gcd(i,j)$
$$=\sum_{d=1}^{n}d\sum_{i=1}^{n}\sum_{j=1}^{n}ij[gcd(i,j)=d]$$
后半部分提出$d$
$$=\sum_{d=1}^{n}d^3\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}ij[gcd(i,j)=1]$$
使用莫比乌斯反演的套路
$$=\sum_{d=1}^{n}d^3\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}ij\sum_{k|gcd(i,j)}\mu(k)$$
先枚举k
$$=\sum_{d=1}^{n}d^3\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)k^2\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}ij$$
$$=\sum_{d=1}^{n}d^3\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)k^2(\frac{\lfloor\frac{n}{kd}\rfloor(\lfloor\frac{n}{kd}\rfloor+1)}{2})^2$$
设$s(n)=\frac{n(n+1)}{2}$
$$=\sum_{d=1}^{n}d^3\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)k^2s^2(\lfloor\frac{n}{kd}\rfloor)$$
令$T=kd$
$$=\sum_{d=1}^{n}d\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(\frac{T}{d})T^2s^2(\lfloor\frac{n}{T}\rfloor)$$
先枚举T
$$=\sum_{T=1}^{n}T^2s^2(\lfloor\frac{n}{T}\rfloor)\sum_{d|T}\mu(\frac{T}{d})d$$
$$=\sum_{T=1}^{n}T^2s^2(\lfloor\frac{n}{T}\rfloor)\sum_{d|T}\mu(\frac{T}{d})id(d)$$
有套路$\mu*id=\varphi$
$$=\sum_{T=1}^{n}T^2s^2(\lfloor\frac{n}{T}\rfloor)\varphi(T)$$
于是就变得可做了
而通过另一个套路
$$n=\sum_{d|n}\varphi(d)$$
我们可以获得一种更简单的做法
$$\sum_{i=1}^{n}\sum_{j=1}^{n}ij·gcd(i,j)$$
$$=\sum_{i=1}^{n}\sum_{j=1}^{n}ij\sum_{d|gcd(i,j)}\varphi(d)$$
$$=\sum_{d=1}^{n}\varphi(d)\sum_{d|i}\sum_{d|j}ij$$
$$=\sum_{d=1}^{n}\varphi(d)d^2\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ij$$
$$=\sum_{d=1}^{n}\varphi(d)d^2s^2(\lfloor\frac{n}{d}\rfloor)$$
所以我们在面对不同的题时，多考虑几种不同的反演方式会使做题速度更快
## 杜教筛
设两个积性函数$f,g$
设另一个积性函数$h=f*g$
记$s(n)=\sum_{i=1}^n f(i)$
$$\sum_{i=1}^n h(i)=\sum_{i=1}^{n}\sum_{d|i}f(d)g(\lfloor\frac{i}{d}\rfloor)$$
转换枚举方式
$$=\sum_{d=1}^n g(d)·\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)$$
$$=\sum_{d=1}^n g(d)·s(\lfloor\frac{n}{d}\rfloor)$$
提出第一项
$$\sum_{i=1}^n h(i)=g(1)·s(n)+\sum_{d=2}^n g(d)·s(\lfloor\frac{n}{d}\rfloor)$$
转换一下
$$g(1)·s(n)=\sum_{i=1}^n h(i)-\sum_{d=2}^n g(d)·s(\lfloor\frac{n}{d}\rfloor)$$
h可以通过前缀和求，而后半段对g求前缀和，s可以进行数论分块
我们处理前$\sqrt{n}$个前缀和可以达到$o(n^{\frac{3}{4}})$的时间复杂度
而经一些巨佬分析可知
处理前$n^{\frac{2}{3}}$个前缀和可以达到更优秀的$o(n^{\frac{2}{3}})$的时间复杂度
例题1
求
$$s(n)=\sum_{i=1}^{n}\mu(i)$$
解
考虑套路式$\mu*I=\epsilon$
$$s(n)=1-\sum_{d=2}^{n}s(\lfloor\frac{n}{d}\rfloor)$$
例2
求
$$s(n)=\sum_{i=1}^{n}\varphi(i)$$
解
考虑套路式$\varphi*I=id$
$$s(n)=\sum_{i=1}^{n}id(i)-\sum_{d=2}^ns(\lfloor\frac{n}{d}\rfloor)$$
$$=\frac{n(n+1)}{2}-\sum_{d=2}^ns(\lfloor\frac{n}{d}\rfloor)$$
例3
求
$$s(n)=\sum_{i=1}^{n}\varphi(i)i$$
解
设$g(n)=i$
此时
$$(f*g)(n)=\sum_{d|n}\varphi(d)·d·(\frac{n}{d})$$
$$=\sum_{d|n}\varphi(d)n$$
$$=n^2$$
于是
$$s(n)=\sum_{i=1}^ni^2-\sum_{i=2}^ns(\lfloor\frac{n}{d}\rfloor)·i$$
$$s(n)=\frac{n(n+1)(2n+1)}{6}-\sum_{i=2}^ns(\lfloor\frac{n}{d}\rfloor)·i$$
就变得可做了
杜教筛的核心就是抓住套路式，对于一个需要求的$f$的前缀和，我们找出一个合适的$g$便可做了
## min_25筛
这个算法针对一类乘性函数的求和问题，这类函数满足它质数及质数次幂的值可以很容易地求出来
通常是一个极其简单的多项式（至少是完全奇性的，并且能够快速求出$g(n,0)$,设其为$f(x)$）
例
求
$$\sum_{i=1}^{n}F(i)$$
我们先不管这个$F$,我们先来计算
$$\sum_{i=2}^{n}f(i)$$
对这个质数构成的多项式求和
定义$g(n,j)$表示一些数的f(i)的和，这些数是质数或者最小质因子>$P_j$的数
我们怎么推这个$g$呢
首先对于$P_j^2>n$的情况，假定$P_{j-1}^2<=n$
如果它不是质数，则需要最小质因子至少大于$P_{j-1}$也就是$P_j$
所以这个数至少是$P_j^2$，已经不在范围内了
所以不需要筛掉其他的数了
即
$$g(n,j)=g(n,j-1)\space\space(P_j^2>n)$$
如果是$P_j^2<=n$的情况呢
我们此时就需要筛掉最小质因子为$P_j$的数
所以我们先拿出一个$f(P_j)$,因为是乘性函数所以成立
剩下的便是$\frac{n}{P_j}$,即需要在小于等于这个数的范围内寻找最小质因子$>=P_j$的，即最小质因子$>P_{j-1}$的,即$g(\frac{n}{P_j},j-1)$
$$g(n,j)=g(n,j-1)-f(P_j)·g(\frac{n}{P_j},j-1)$$
但是我们就会发现，我们同时也把那些$<P_j$的质数也筛掉了，而这些数乘上$P_j$会出现一些最小质因子$<P_j$的数，而这些数我们不能再筛，所以我们需要还原它们，即$g(P_j-1,j-1)$
$$g(n,j)=g(n,j-1)-f(P_j)·(g(\frac{n}{P_j},j-1)-g(P_j-1,j-1))\space\space(P_j^2<=n)$$
于是我们就把$g$推出来了
定义
$$S(n,j)=\sum_{i=2}^nF(i),min(p_i)>=P_j$$
表示$S(n,j)$是一些数的$F(i)$的和，其中i的最小质因子大于等于$P_j$
我们首先考虑质数的贡献
$$g(n,|P|)-g(P_j-1,j-1)$$
这个贡献必须除去最小质因子小于$P_j$的情况，即$g(P_j-1,j-1)$
然后考虑合数的贡献
我们枚举每个合数的最小质因子的次幂是多少，然后往下递推计算贡献，同时我们也应该考虑合数只由最小质因子构成的情况，即
$$\sum_{i=j}^{P_i^2<=n}\sum_{k=1}^{P_i^{k+1}<=n}(F(P_{i}^k)S(\frac{n}{P_i^k},i+1)+F(P_i^{k+1}))$$
合在一起就是
$$S(n,j)=g(n,|P|)-g(P_j-1,j-1)+\sum_{i=j}^{P_i^2<=n}\sum_{k=1}^{P_i^{k+1}<=n}(F(P_{i}^k)S(\frac{n}{P_i^k},i+1)+F(P_i^{k+1}))$$
最后就会发现
$$\sum_{i=1}^nF(i)=S(n,1)+f(1)$$
得到结果
$g$函数可以通过递归或者递推求出，$S$函数可以递归求出
理论时间复杂度为$o(\frac{n^{\frac{3}{4}}}{log\space n})$,可以解决$n$的数量级为$10^{10}$左右的求和问题