数论
Published:
数论
一.完全积性函数
1.元函数
$ \epsilon(n)=[n==1] $
2.恒函数
$ I(n)=1 $
3.单位函数
$ id(n)=n $
二.积性函数
1.欧拉函数
定义 $\phi(x)$ 为不超过 $x$ 的自然数中与 $x$ 互质的数的个数
易知 $ \displaystyle \phi(x)=x\Pi _{i=1}^n (1-\frac{1}{p_i} ) $
关于欧拉函数的一些性质:
若 $x$ 为质数，$ \phi(x)=x-1 $
若 $x$ 与 $y$ 互质， $ \phi(xy)=\phi(x)\phi(y) $
若 $ x\%p=0 $，$ \phi(xp)=\phi(x)p $
| $\displaystyle x=\sum_{d | x}\phi(d) $ ，即 $ \phi*I=id $ |
$ a^b\%p=a^{b\%\phi(p)}\%p $
2.莫比乌斯函数
当 $d=1$，$ \mu(d)=1 $
当 $d=\Pi_{i=1}^k p_i $，$ p_i $为互异质数，$\mu(d)=(-1)^k $
当 $ d $ 中任意一个质因子个数大于等于 $2$ ，$ \mu(d)=0 $
关于莫比乌斯函数的一些性质:
$ gcd(a,b)==1 $ ，$ \mu(ab)=\mu(a)\mu(b) $
| $ \displaystyle \sum_{d | n}\mu(d) = [n==1] $ ，即 $ I*\mu=\epsilon $ |
| $ \displaystyle \sum_{d | n} \frac{\mu(d)} {d} = \frac {\phi(n)}{n} $，即 $ \mu * id=\phi $ |
3.约数个数函数
| $ \displaystyle d(n)=\sum_{d | n}1 $ |
| $ \displaystyle d(x*y)=\sum_{a | x} \sum_{b | y} [gcd(x,y)==1] $ |
三.狄利克雷卷积
| $ \displaystyle h*g=\sum_{d | n}f(d)g(\frac{n}{d} ) $ |
四.莫比乌斯反演
| $ \displaystyle F(n)=\sum_{d | n}f(d) $ $ \Rarr $ $ f(n)=\sum_{d | n}\mu(\frac{n}{d})F(d) $ |
| $ \displaystyle F(n)=\sum_{n | d}f(d) $ $ \Rarr $ $ f(n)=\sum_{n | d}\mu(\frac{d}{n})F[d] $ |
五.杜教筛
求积性函数 $ f $ 的前缀和 $ \displaystyle \sum_{i=1}^n f(i) $
设积性函数 $ g $ 、$ h $，使 $h=g*f $，求 $ \displaystyle \sum_{i=1}^n h(i) $，记$ \displaystyle S(n)=\sum_{i=1}^n f(i) $ 。
| $\displaystyle \sum_{i=1}^n h(i) = \sum_{i=1}^n \sum_{d | i} g(d)*f(\frac{i}{d}) $ 。 |
$\displaystyle \sum_{i=1}^n h(i) = \sum_{d=1}^n g(d) \sum_{i=1}^{\frac{n}{d}} f(i) $ 。
$ \displaystyle \sum_{i=1}^n h(i) = \sum_{d=1}^n g(d) * S(\frac{n}{d}) $ 。
将第一位提出来 $ \displaystyle \sum_{i=1}^n h(i) = g(1)*S(n) + \sum_{d=2}^n g(d) * S(\frac{n}{d}) $
$ \displaystyle g(1)*S(n)= \sum_{i=1}^n h(i) - \sum_{d=2}^n g(d) * S(\frac{n}{d}) $
当 $ h(i) $的前缀和好求，对后式整除分块。
补充一点积性函数之间的关系：
$ \mu * I = \epsilon $
$ \phi * I = id $
$ \mu * id = \phi $
六.min_25筛
七.其他结论
$ \displaystyle f(x)=\sum_{i=1}^x i\epsilon(gcd(i,x))=\frac{x( \phi(x)+\epsilon(x) )}{2} $
$ \displaystyle g(x)=\sum_{i=1}^x \sum_{j=1}^x i * j * \epsilon(gcd(i,j))=\sum_{i=1}^x i^2 * \phi(i) $
| $minmax$ 容斥：$ \displaystyle max(S)=\sum_{T \subseteq S}min(T)*(-1)^{ | T | +1} $ |
| $minmax$ 容斥：$ \displaystyle min(S)=\sum_{T \subseteq S}max(T)*(-1)^{ | T | +1} $ |