因子和倍数问题

Published: April 13, 2021 by Daltao

• Categories:
• algorithm 101

• Tags:

• 因子和倍数问题
• 素数
  • 素数筛
• 统计因子和倍数的方式

因子和倍数问题

简单记$\phi(x)$表示$x$的因子数。

题目1：给定正整数$g$，找到$g$的所有素因子。其中$1\leq g\leq 10^{18}$。

首先考虑如何找到给定数$g$的所有素因子。这个用Pollard Rho算法就可以了，时间复杂度为$O(g^{1/4}(\log_2g)^2)$，但是实际上跑的飞快。

题目2：给定正整数$g$，要求找到$g$的所有因子。其中$1\leq g\leq 10^{18}$。

先找到所有素因子，之后可以直接暴力递归搜它的所有因子。后者时间复杂度为$O(\phi(x))$。注意这里$\phi(x)$只有10万级别大小。

题目3：给定正整数$g$，以及数$p$，其中$gcd(g,p)=1$。要求找到最小的正整数$x$满足$g^x=1\pmod p$。其中$1\leq g,p\leq 10^{9}$

由欧拉定理知$g^{\varphi(p)}=1\pmod p$，利用辗转法不难得知$x\mid \varphi(p)$。因此我们只需要从$\varphi(p)$开始递减即可，不断删除一些素因子，直到不能删为止。在计算出$\varphi(p)$后，接下来的时间复杂度为$O((\log_2p)^2)$。

题目4：给定正整数$g$，考虑$g$的所有因子。接下来处理$n$个元素$x_1,\ldots,x_n$，其中$x_i$是$g$的因子。之后对所有$g$的因子$d$，计算$x$中有多少数是是$d$的因子。

可以发现整除关系可以构成一个非常庞大的有向图，很难搞。但是整除关系实际上原本有向图简单规则得多。

考虑唯一的素数分解$g=p_1^{c_1}\ldots p_k^{c_k}$。我们可以用向量$(c_1,\ldots,c_k)$来唯一表示$g$。这时候所有$g$的因子也可以如法表示。现在问题变成了一个高维数组前缀和。后者计算的时间复杂度为$O(k\phi(g))$。

题目5：给定正整数$g$。之后给定$n$个数$x_1,\ldots,x_n$，要求计算$\cup_{i=1}^n\left\{kx_i\pmod g\mid k\geq 0\right\}$的大小。其中$1\leq g\leq 10^9$，$1\leq n\leq 10^5$

实际上$x_i$的意义是将所有$gcd(x_i,g)$的倍数全部标记。而问题要求我们计算有多少数最终被标记。接下来我们可以认为$x_i=gcd(x_i,g)$。

首先对数据进行去重。如果我们直接维护bitset暴力计算的话，时间复杂度为$O(\sum_{d\mid g}d)$，它的值约为$O(g\ln\ln g)$。不是很大。

还有一种更加高效的方式是发现$\phi(g)\leq 1200$。我们可以根据容斥计算。记录$dp(i,j)$表示仅考虑$x_1,\ldots,x_i$，被选中的元素的最小公倍数为$j$，总共的方案数（带符号，选择奇数次为正号，偶数次为负号）。其对外的贡献只有两种，因此可以$O(\phi(g)^2\log_2g)$计算。

最终的结果为$\sum_{d\mid g}dp(n,d)\times \frac{g}{d}-n$。

素数

素数是指大于$1$，且除了$1$和自身外，没有其它因子的整数。

$\pi(x)$表示所有小于等于$x$的正整数中素数的数目，在$x$足够大的时候，$\pi(x)\approx \frac{x}{\ln x}$。

素数筛

素数筛用于查找所有小于等于$n$的所有素数。下面给出一些筛法以及对应的时间复杂度：

• 暴力判断每个数是否是素数，时间复杂度为$O(n\sqrt{n})$。
• 欧拉筛，时间复杂度为$O(n)$。
• 暴力枚举所有数的倍数，并标记它们为合数，时间复杂度为$O(n\ln n)$。
• 埃拉托斯特尼筛法，暴力枚举所有素数的倍数，并标记它们为合数。时间复杂度为$O(n\ln\ln n)$。

统计因子和倍数的方式

考虑这样一个问题，给定一个数组$a_1,\ldots,a_n$，每个数都大于等于$1$，且不超过$M$。且$1\leq n,M\leq 10^7$。

记$f(x)=\sum_{i=1}^n[a_i|x]$，即序列$a$中有多少数是$x$的因子。

要求输出$f(1),\ldots,f(M)$。

首先我们记$c(x)$表示$x$在$a$序列中出现的次数。之后考虑如何解决这个问题。

这个问题有很多做法，最简单的是枚举所有的因子，这样可以给出$O(M\sqrt{M})$的时间复杂度。

还有一种做法，就是我们仅考虑每个数的所有倍数，并进行统计。这样时间复杂度为$O(M\ln M)$的时间复杂度。

还有一种做法，就是我们考虑所有素数的倍数，并进行统计。这样时间复杂度为$O(M\ln\ln M)$。

这里我们仅详细讲一下最后一种方式，这种方式我是从这个评论学到的。代码如下：

let primes be all prime of [1, M];
f = g;
for(p in primes) {
    for(i = 1; i * p <= M; i++){
        f[i * p] += f[i];
    }
}

记$p_i$表示第$i$小的素数，很显然时间复杂度为$\sum_{i=1}^{\pi(M)} \frac{M}{p_i}$，根据素数定理，$\pi(M)\approx \frac{M}{\ln M}$，因此$p_{\pi(M)}\approx M$，可以得出$p_x\approx x\ln x$。代入进去可以得到：

$$\begin{aligned} &\sum_{i=1}^{\pi(M)} \frac{M}{p_i}\\ \approx &M\sum_{i=2}^{\pi(M)} \frac{1}{i\ln i}\\ \approx &M\int_{i=2}^{\pi(M)}\frac{1}{x\ln x}\mathrm{d}x\\ \approx &M [\ln \ln x]_2^{\pi(M)}\\ \approx &M\ln\ln M \end{aligned}$$

因此可以得出时间复杂度为$O(M\ln \ln M)$。

现在我们考虑算法的具体含义。记$f_i$表示处理完第$i$个素数后$f$数组的取值。这时候有$f_0=c$，$f_1(x)=\sum_{k}f_0(\frac{x}{p_1^k})$。

$$\begin{aligned} f_2(x)&=\sum_{k}f_1(\frac{x}{p_2^k})\\ &=\sum_{k}\sum_{j}f_0(\frac{x}{p_2^kp_1^j}) \end{aligned}$$

换言之$f_t(x)$表示$x$枚举所有$i_1,\ldots,i_t$，$c(\frac{x}{\prod_{j=1}^tp_j^{i_j}})$的和。而$f_{\pi(M)}(x)$自然就是所有$x$的因子和。

我们提到的这个问题是统计因子的，但是统计倍数也可以用类似的做法优化到$O(M\ln\ln M)$。