数论函数相关
前言 :
由于本人脑子生锈严重 , 所以整理了这个东西拯救一下自己的数学
然而问题在于下文的很多问题我都没有完全理解完全没有理解 , 所以出锅概率极高99.99%
所以如果您在阅读过程中发现我出锅了的话 , 请联系我修锅QQ: 2362687579 ,邮箱 : 2362687579@qq.com验证的话就写"辣鸡dntkm出来挨打"就好了quq
积性函数
若对于函数\(f\)在\(gcd(a,b)=1\)时，有\(f(a*b)=f(a)*f(b)\)，则称\(f\)为积性函数
特别的，若函数\(f\)无论\(gcd(a,b)\)，都有\(f(a*b)=f(a)*f(b)\quad\)则称\(f\)为完全积性函数
*注：目前常用的数论函数多为积性函数
Dirichlet卷积
定义两个数论函数的Dirichlet卷积为：
\[ (f * g)(n) = \sum_{d|n}f(d)*g(\frac{n}{d}) \]
满足：
交换律： \((f*g)=(g*f)\)
结合律： \((f*g)*h=f*(g*h)\)
分配律： \((f+g)*h=f*h+g*h\)
*注：两个积性函数的Dirichlet卷积仍为积性函数大概把它当成长得比较奇怪的乘法就好
常见数论函数（积性）
莫比乌斯函数 \(\mu\)
\[\mu(d) \quad = \quad \begin{cases} 1\quad\qquad(d=1) \\ (-1)^{k}\quad(d=p_1p_2...p_k,\forall p_i \neq p_j) \\ 0 \quad\qquad (otherwise) \end{cases}\]
莫比乌斯函数的性质
\[\sum_{d|n}\mu(d) \quad = \quad [n=1] \qquad \quad \begin{cases}1\quad(n=1) \\0\quad(n\neq1)\end{cases} \\ \quad \\ 写为Dirichlet卷积形式为：\mu*I=\epsilon\\ \quad \\ 即：(\mu*I)(n)= \sum_{d|n}\mu(d)*I(\frac{n}{d})\\ = \sum_{d|n}\mu(d) = [n=1] = \epsilon(n) \\ 证 : \sum_{d|n} \mu(d) = \sum_{k=0}^{s} (-1)^k C_{s}^{k} = (1-1)^s = 0 \]
欧拉函数 \(\varphi\)
\[ \varphi(n) \quad = \quad \sum_{i=1}^{n} \quad [gcd(n,i) = 1]\]
欧拉函数的性质
\[\sum_{d|n}\varphi(d) \quad = \quad n \qquad \quad \\ \quad \\
写为Dirichlet卷积形式为：\varphi*I=id\\ \quad \\
即：(\varphi*I)(n)= \sum_{d|n}\varphi(d)*I(\frac{n}{d})\\
= \sum_{d|n}\varphi(d) = n = id(n) \\
证 : \sum_{d|n} \varphi(d) = \sum_{d|n} \varphi(\frac{n}{d}) = \sum_{d|n} \sum_{d|i}^{\frac{n}{d}} [gcd(\frac{n}{d},\frac{i}{d})==1] \\
\quad = \sum_{d|n} \sum_{i=1}^{n} [gcd(n,i)==d] = n \\
注 : 即枚举了gcd(n,i)的所有情况 , 那么每个i贡献为1 , 求和即为n \\
\]
\[
\sum_{d|n}d\varphi(\frac{n}{d}) \quad = \quad \sum_{i=1}^{n}gcd(i,n) \\
写为Dirichlet卷积形式为：\varphi*id= \sum_{i=1}^{n}gcd(k,n) \\ \quad \\
证: \sum_{d|n}d\varphi(\frac{n}{d}) \quad = \quad \sum_{d|n} d \sum_{i=1}^{\frac{n}{d}}[gcd(i,\frac{n}{d})=1]\\
= \sum_{d|n} d \sum_{i=1}^{\frac{n}{d}}[gcd(i*d,n)=d] = \sum_{i=1}^{n}gcd(i,n)
\]
约数个数和函数 \(d\)
\[ d(n) \quad = \quad \sum_{d|n} \quad 1\]
约数和函数 \(\sigma\)
\[ \sigma(n) \quad = \quad \sum_{d|n} \quad d \]
常见数论函数（完全积性）
元函数 \(\epsilon\)
\(\quad \epsilon(n) \quad = \quad [n=1]\)
元函数的性质:\(\quad f*\epsilon(n)=f\)
恒等函数 \(I\)
\(\quad I(n) \quad = \quad 1\)
单位函数 \(id\)
\(\quad id(n) \quad = \quad n\)
莫比乌斯反演相关
莫比乌斯反演
\[ \begin{aligned} 设: &若有:数论函数 f,F \\ &已知: f=F*I=\sum_{d|n}F(d) \\ &则有: F=f*\mu=\sum_{d|n}\mu(d)*f(\frac{n}{d}) \\ &证明: f*\mu=F*(I*\mu)=F*\epsilon=F \\ \end{aligned}\]
杜教筛相关
杜教筛
待填坑 咕咕咕
时间复杂度
使用Eula筛处理前\(n^{\frac{2}{3}}\)项时复杂度最优
其复杂度为\(O(n^{\frac{2}{3}})\quad\)(请手写Hash表)
常用套路式
我只是看到过 , 不一定"常用"
\[ d(ij) = \sum_{x|i}\sum_{y|j} [gcd(x,y)=1]\]
\[ \sum_{k=1}^{n} d(k) = \sum_{k=1}^{n} \sum_{d|k} 1 = \sum_{d=1}^{n} \lfloor \frac{n}{i} \rfloor \]
\[ \sum_{x=1}^{n}\sum_{y=1}^{m} [gcd(i,j) = 1] = \sum_{d=1}^{min(n,m)} \mu(d) \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor \]
\[ [gcd(i,j)=1] = \sum_{d|i,d|j} \mu(d) \]