How to find the GCDs of LCMs of all pairs of elements in the given sequence.

Question

You are given a sequence $A$ of positive numbers where the number will not be larger than $200,000$. A multiset is created from the given sequence such that: $S = \{LCM(a_{i}, a_{j}) \;|\; i < j\}$. Design an algorithm that computes the $GCD(S)$.

Constraints
$1 \leq length(A) \leq 10^{5}$
$1 \leq a_{i} \leq 2 \times 10^{5}$ where $a_{i}$ represents the elements of the sequence $A$.

For Example:

1. $A = \{10, 24, 40, 80\}$ then the multi-set $S$ for the given sequence will be $S = \{120, 40, 80, 120, 240, 80\}$ and $GCD(S) = 40$.
2. $A = \{540, 648, 810, 648, 720\}$ then the multi-set $S$ for the given sequence will be $S = \{3240, 1620, 3240, 2160, 3240, 648, 6480, 3240, 6480, 6480\}$ and $GCD(S) = 108$.

I can't think of an algorithm that has a time-complexity better than $O(n^{2}\;log(a_{i},b_{i}))$ where $a_{i}, b_{i}$ are pairs of numbers considered and $log()$ is due to fact that for the calculation of $LCM(a, b)$ we need to compute $GCD(a, b)$ and time complexity of computing $GCD(a, b)$ using Eucledian Algorithm is $O(log(a \times b))$.

Answer 1

Given a prime $p$, its power in the gcd's of lcm pairs is simply the second-lowest power of $p$ in the list.

For instance, in your second example $A = \{540, 648, 810, 648, 720\}$, the powers of $3$ are $\{3,4,4,4,2\}$. The second-lowest number in this multi-set $3$, so the power of $3$ in the result is $3$. (Here it is important that we consider a multiset, because if the lowest number occurs twice, we want it to count as the second-lowest.)

So you just have to maintain a list of the lowest two powers so far found, for each prime, and factorise each element of $A$, updating the list as you go.

Answer 2

For a prime number $p$ and an integer $n$, we write $v_p(n)$ for the $p$-adic valuation of $n$, i.e. the exponent of $p$ in the factorisation of $n$.

It is easy to see that $v_p(\gcd(S))$ is the second smallest element of $\{v_p(a): a \in A\}$.

Hence an algorithm goes as follows:

1. Factorize the first two elements in $A$. Let $P$ be the set of prime numbers appearing in at least one of these two factorizations. It is clear that $P$ is a quite small set ($< 15$). Also, any prime factor of $\gcd(S)$ must be in $P$.
2. Go through the sequence $A$, keeping a record of the smallest and second smallest exponents for every $p\in P$.