问题描述

给出含有\(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)\)