Ahead
10.9.2018
前置知识
数论函数
指一个正整数集对一个数集的映射 可以看成 N+->R
加法
若函数 \(f(x) + g(x) = h(x)\) 那么 \(h(x) = \sum_{i=1}^n{f(i)+g(i)}\)
即对应项相加数乘
若函数$ x f(x) = (xf)(n) $
即对每一项系数都乘x狄利克雷卷积
可以看成是函数的乘法
若 $ t = f *g $ 即 t 为f卷g的结果 那么 有 \[ h(n) = \sum_{i|n}{f(i)g(\frac{n}{i})} \] 或者是 \[ h(n) = \sum_{ij==n}{f(i)g(j)} \] 类似是做了一种乘法，有点像叉积= =类比一下，这个大概的背一下还是很好记的性质
- 满足交换律 \(h= a*b = b*a\)是一样的（参见上面的公式）
- 满足结合律 \(h= （a*b）*c = a*（b*c)\) 可以看成n的三个数分解
- 分配律 \((f+g）*h = f*h +g*h\) 因为狄利克雷卷积针对的是单项，所以f和g先加起来再乘的项和先乘再加的结果是一样的（代点例子就看出来了）
数乘结合律 \(xf *g = x(f*g)\) 用上面的分配律正反各一遍
基本数论函数
\(\mu(n)\) 莫比乌斯函数 下面介绍
\(\phi(n)\) 欧拉函数 不大于n的与n互质的个数\(\epsilon(n)\) 元函数 \(\epsilon(n) = [n==1]\) 即n=1时为1 否则为0\(\iota(n)\) 恒等函数 永远为1\(id(n)\) 单位函数 \(id(n)==n\)积性函数
\(f(n*m)=f(n)*f(m)\) 上面提到的欧拉函数就是一种，值得注意的是如果一个函数是两个积性函数卷积而来的，那么这个函数也是积性函数
PF：\[h(n*m)= \sum_{d|n*m}{f(d)g(\frac{n*m}{d})} \]\[\quad\quad\quad\quad= \sum_{i|n,j|m}{f(ij)g(\frac{n*m}{i*j})}\]\[\quad\quad\quad\quad\quad\quad= \sum_{i|n,j|m}{f(i)f(j)g(\frac{n}{i})g(\frac{m}{j})}\]\[\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad=\left( \sum_{i|n}{f(i)g(\frac{n}{i})} \right)\left( \sum_{j|m}{f(j)g(\frac{m}{j})} \right) \]\[=h(n)h(m)\]函数的逆函数
即若\(f*g=\epsilon\)则f，g互为逆函数，（BTW） 如果f为积性函数，那么g也为积性函数
莫比乌斯反演
我们定义函数\[F(n)=\sum_{d|n}{f(d)}\]
那么我们可以反演出 \[f（n）=\sum_{d|n}{\mu(\frac{n}{d})F(d)}\]推导
有\[F(n)=\sum_{d|n}{f(d)}\] （这个式子和卷积很想把）
可以看成\[F(n)=\sum_{d|n}{f(d)}{1}\] 即\[F(n)=\sum_{d|n}{f(d)}{\iota(\frac{n}{d})}\] 化简一下就是\[F=f*\iota\] 两边同时乘上\(\mu\) 有 \[F*\mu = f*\iota *\mu \] 也就是 \[f*(\iota *\mu) = f*\epsilon = f \] 下面证明 \(\iota *\mu=\epsilon\) 首先，什么是莫比乌斯函数\[ \mu(d)=\begin{cases} 1 & d==1 \\ (-1)^k & 分解质因数后只有一次幂，k为质因数个数 \\ 0 & 剩下的 \end{cases}\] 一个性质\[\sum_{d|n}{\mu(d)}=\epsilon\] 当n==1 是 显然成立 当n>=1 时 有\[d=p1^{a1}\times p2^{a2}\times p3^{a3}\times \ldots\times pk^{ak}\] 如果其中有一个\(ai\)大于0 那么得出的\(\mu\)为0(定义) 所以\(\sum_{d|n}{\mu(d)}\) 就等于从k个质因子中取奇数个（-1）和偶数个（1） 的和 式子表示就是\[\sum_{d|n}{\mu(d)} = \sum_{i=0}^k{(-1)^k C_k^i}\] 根据二项式定理 原式就是\[ \sum_{i=1}^k{(-1)^k C_k^i} = ((x=1)+(y=-1))^n = 0^n \] 证毕 那么由\[\sum_{d|n}{\mu(d)}=\epsilon\] 可以推出 \[\epsilon = \sum_{d|n}{\mu(d)} * \iota (\frac{n}{d})\] 简写就是上面的式子了 所以莫比乌斯反演成立代码
线筛莫比乌斯函数
void get_mu(int n){ mu[1]=1; for(int i=2;i<=n;i++) { if(!vis[i]){prim[++cnt]=i;mu[i]=-1;} for(int j=1;j<=cnt&&prim[j]*i<=n;j++) { vis[prim[j]*i]=1; if(i%prim[j]==0)break; else mu[i*prim[j]]=-mu[i]; } } }