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]$内每个数是否为素数.

利用"唯一素数分解"的性质, 我们尝试让每个数只被更新一次:

0. 若一个数没有被标记, 这个数为素数.
1. 对于每个数$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.$$