Note2020.09.22一点数论
摘要： 本文主要介绍了数论中的一些基本概念和算法，包括素数判定、因数个数、线性筛、最小素因数、欧拉函数、欧拉函数线性筛等。同时，文章还给出了每个算法的复杂度分析和证明。
本文由 徐锦涛小哥哥 支持撰写
素数判定
求因数个数
线性筛
求最小素因数
欧拉函数
欧拉函数线性筛
のののののの
素数の判定
如何判断一个数$x$是否为素数？（单次查询）
暴力地，我们用$[2,\lceil\sqrt{N}\rceil]$内的数对$x$进行判断，如果区间内存在一个$y$满足$y|x$，则$x$为合数，反之则为素数。
复杂度$O(\sqrt{N})$
唯一の素数分解
显而易见的, 一个整数一定能分解为若干个素数$p$的积, 即一个数的唯一素数分解：
$$ x= \prod{p_{i}^{k_i}} $$
求唯一の素数分解
那么我们如何求出一个数的素数分解呢? (此时我们并不知道有哪些素数)
类似素数判定中的做法, 用$O(\sqrt{N})$的复杂度升序对$x$进行试除, 若存在$y$使得$y|x$, 我们让$x=x \div y$. 若依旧$y|x$, 继续如此做.
对于相同的$y$, 我们统计它出现的次数.
感性理解可以发现:每次求得的$k$一定是一个素数$p$, 统计的出现次数则为这个素数的指数$k$.
证明: 如果存在一个$y$可以分解为两个(或以上)的素数$p_1,p_2......$, 对于其中任意$p$必有$p<y$. 若是如此, 这个素数$p$一定会在前面出现.
复杂度$O(\sqrt{N})$
有多少因数? I
如何求一个数的因数个数?
将一个数分解$x$后的素数表示为一个multiset$P$, 任意非空素数集合$S \in P$中元素的乘积$y$都是$x$的因数.
考虑$x$的某个素因数$p$取用的数量, 总因数个数为$\prod{k_i+1}$.
使用上面的方法进行素数分解, 我们可以得到每一个的指数.
复杂度$O(\sqrt{N})$
线性筛
$O(N)$求出$[1,N]$内每个数是否为素数.
利用"唯一素数分解"的性质, 我们尝试让每个数只被更新一次:
- 若一个数没有被标记, 这个数为素数.
- 对于每个数$x$, 我们遍历一次素数表$p$, 并标记$x·p_i$.
预处理$O(N)$, 查询$O(1)$.
最小の素因子
求一个数的最小素因子.
好像跟线性筛没啥关系, 但是它确实能用线性筛解决.
考虑在线性筛的时候, 维护一个$f_i$表示$i$的最小素因子($p$为某一素数):
$$ \left\{ \begin{aligned} f_i &= i & (i = p) \\ f_i &= f_j & (i = j \times p) \end{aligned} \right. $$
预处理$O(N)$, 查询$O(1)$.
有多少因数? II
这个问题我们已经熟悉了, 这次我们也考虑对一个数进行唯一素数分解.
现在我们已经能够在线性时间内得到每个数的最小素因子了, 可以它对一个数$x$进行分解, 只要不停地使$x=x \div f_x$.($f_i$表示$i$的最小素因子)
显然我们得到的素数是升序的(最小素因子), 那么指数也很方便统计.
证明这个算法的复杂度不会很高, 考虑两个问题.
一个数最多有多少素因子?
我们使素因子尽量小, 假定都为$2$. 可以发现, $x$的素因子个数最大数量级大约为$log_2x$.
一个数最多有多少因数?
一个比较显然的结论:不同的素因子更多时, 因数个数更多.
我们可以暴力地升序枚举每一个素数, 并将他们乘起来$\prod{p_i}$. 可以发现, 这个数增长地很快, 当$i=9$时这个数就已经超过了$10^9$.
预处理$O(N)$, 查询$O(log_2x)$.
欧拉函数
定义: 欧拉函数$φ(x)$表示小于$x$与$x$互质的数的数量.
欧拉函数の积性
定义: 对于$f(x)$, 若当$(x,y)=1$时$f(xy)=f(x)f(y)$, $f(x)$是积性函数.
众所周知, $φ$是积性函数, 但为什么是积性函数呢?
a 若$p$是素数, $\phi(p)=p-1$
结论显然
b 若$p$是素数, $φ(p^k)=p^k - p^{k-1}$
考虑容斥, 从$p^k$个正整数中减去$p$的因数. 因为只有一个素因子$p$, 所有$p$的倍数均为$p^k$的倍数, 且其他数均不是$p^k$的倍数. 这样的数共有$p^k \div p = p^{k-1}$个.
c 若$p_1,p_2$是素数, $φ(p_{1}^{k_1}·p_{2}^{k_2})=φ(p_{1}^{k_1})·φ(p_{2}^{k_2})$
类似$b$, 我们考虑容斥.
因为$(p_{1}^{k_1},p_{2}^{k_2})=1$, 重复的部分只有$p_1p_2$的倍数. 式子为:
$$ \phi(p_{1}^{k_1}·p_{2}^{k_2})=p_{1}^{k_1}·p_{2}^{k_2}-p_{1}^{k_1-1}·p_{2}^{k_2}-p_{1}^{k_1}·p_{2}^{k_2-1}+p_{1}^{k_1-1}·p_{2}^{k_2-1} $$
通过$b$我们可以分别求出$φ(p_{1}^{k_1})=p_{1}^{k_1}-p_{1}^{k_1-1}$和$φ(p_{2}^{k_2})=p_{2}^{k_2}-p_{2}^{k_2-1}$.
显然将他们乘起来是等于上面那个式子的, 得证.
d 欧拉函数$φ$是积性函数
考虑将$c$扩展到多个素因数$p$的情况, 做类似的容斥.
对容斥得到的式子做因式分解, 可以得到下面这个式子:
$$ φ(x)=\prod{p_{i}^{k_i-1}(p_i-1)} $$
求$φ$の方
对上一部分$d$中的式子提公因子可得
$$ φ(x)=x\prod_{p|x}{(1- \frac{1}{p})} $$
然后我们用求唯一素数分解的方法求得每个素因数带入公式即可.
复杂度$O(\sqrt{N})$
欧拉函数の线性筛
当然我们也可以通过线性筛求唯一素数分解, 但这次我们还有更强大的算法.
对于素数$p$和数$k$有$(p,k)>1$, $φ(pk)=p·φ(k)$
考虑欧拉函数の积性中的结论$c$:
$$ φ(p_{1}^{k_1}·p_{2}^{k_2})=p_{1}^{k_1}·p_{2}^{k_2}-p_{1}^{k_1-1}·p_{2}^{k_2}-p_{1}^{k_1}·p_{2}^{k_2-1}+p_{1}^{k_1-1}·p_{2}^{k_2-1} $$
如果使$k_1'=k_1+1$, 上述式子只需要变形为
$$ φ(p_{1}^{k_1'}·p_{2}^{k_2})=p_{1}^{k_1+1}·p_{2}^{k_2}-p_{1}^{k_1+1-1}·p_{2}^{k_2}-p_{1}^{k_1+1}·p_{2}^{k_2-1}+p_{1}^{k_1}·p_{2}^{k_2-1} $$
可以得到$φ(p_{1}^{k_1'}·p_{2}^{k_2})=φ(p_{1}^{k_1}·p_{2}^{k_2})·p$.
这个式子也可以被扩展.
好了, 现在我们可以进行线性筛了.
在线性筛中, 如果我们想用一个数$x$和素数数$p$更新$xp$的$φ$, 先判断条件$p|x$即可:
$$ \left\{ \begin{aligned} φ(p) &= p-1 \\ φ(xp) &= φ(x)*(p-1) & (p \nmid x) \\ φ(xp) &= φ(x)*p & (p|x) \end{aligned} \right. $$