快速质因数分解: Atcoder[abc177-E]

快速质因数分解: Atcoder[abc177-E]

问题描述

给出含有\(N\)个元素的数组\(A_i \),若对任意的\(i,j ( 1 \leq i < j \leq N \),都有\(\gcd(A_i,A_j)=1\),则称为个数组为”pairwise coprime”。若这个数组不是 “pairwise coprime”,同时有\( \gcd(A_1,A2,\cdots,A_N)=1\),则称这个数组为”setwise coprime”,否则,此数组为”not coprime”。

  • \(2 \leq N \leq 10^6 \)
  • \(1\leq A_i \leq 10^6\)

分析

为了求解pairwise coprime,利用定义判断需要花\(O(N^2) \)的时间,会得到TLE

将pairwise coprime的条件可以等价表述成“对于任意质数\( p\),\(A_i\)中的p的某个倍数的数仅有1个”(如果\( A_i\)和 \(A_j\)同是p的某个倍数,那么\(\gcd(A_i,A_j)=p\),就不是pairwise coprime了)。

所以可以将\(A_i \)进行质因数分解,来检查\(A_i\)的各个元素是否有质因子重复出现。这样可以使用快速质因数分解,能够达到\( O(A\log\log A + N \log A) \)的时间复杂度( 这里\(A=\max\{A_i\}\) )。

判断setwise coprime的话,直接计算整个数组的\( \gcd \)即可,这一步的时间复杂度为\( O(N \log(A)) \),综上,本题可以在 \( O(A\log\log A + N \log A) \)的时间内解决。

下面是关于快速质因子分解的算法过程。

快速质因数分解

给出最大值为A的N个数字,将这些数进行质因数分解。

首先使用筛法得到质数序列。使用一个数组D保存”最小质数因子”,例如D[4]=D[6]=2,D[35]=5:如果x是素数那么D[x]=x,这个数组和筛法一样是\( O(A \log \log A) \)的时间。

D[x]就是x的因子中最小的素数,利用这个数组进行质因数分解时就减少了不必要的试除法,每个数的质因数分解的时间为\(O(\log A)\)

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注