因子和倍数问题

Published: by Creative Commons Licence

  • 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$。