Orac and LCM
Contest: Codeforces Round 641 (Div. 1)
Difficulty rating: 1600
Tags: data structures, math, number theory

For the multiset of positive integers $$$s=\{s_1,s_2,\dots,s_k\}$$$, define the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of $$$s$$$ as follow:

- $$$\gcd(s)$$$ is the maximum positive integer $$$x$$$, such that all integers in $$$s$$$ are divisible on $$$x$$$.
- $$$\textrm{lcm}(s)$$$ is the minimum positive integer $$$x$$$, that divisible on all integers from $$$s$$$.

For example, $$$\gcd(\{8,12\})=4,\gcd(\{12,18,6\})=6$$$ and $$$\textrm{lcm}(\{4,6\})=12$$$. Note that for any positive integer $$$x$$$, $$$\gcd(\{x\})=\textrm{lcm}(\{x\})=x$$$.

Orac has a sequence $$$a$$$ with length $$$n$$$. He come up with the multiset $$$t=\{\textrm{lcm}(\{a_i,a_j\})\ |\ i<j\}$$$, and asked you to find the value of $$$\gcd(t)$$$ for him. In other words, you need to calculate the GCD of LCMs of all pairs of elements in the given sequence.

Input format:
The first line contains one integer $$$n\ (2\le n\le 100\,000)$$$.

The second line contains $$$n$$$ integers, $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 200\,000$$$).

Output format:
Print one integer: $$$\gcd(\{\textrm{lcm}(\{a_i,a_j\})\ |\ i<j\})$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
For the first example, $$$t=\{\textrm{lcm}(\{1,1\})\}=\{1\}$$$, so $$$\gcd(t)=1$$$.

For the second example, $$$t=\{120,40,80,120,240,80\}$$$, and it's not hard to see that $$$\gcd(t)=40$$$.

Example input:
2
1 1

Example output:
1

Example input:
4
10 24 40 80

Example output:
40

Editorial:
In this tutorial $$$p$$$ stands for a prime, $$$v$$$ stands for the maximum of $$$a_i$$$ and $$$ans$$$ stands for the answer.
Observation. $$$p^k\ \mid\ ans$$$ if and only if there are at least $$$n-1$$$ integers in $$$a$$$ that $$$\mathrm{s.t. }\ p^k\mid\ a_i$$$.
Proof. if there are at most $$$n-2$$$ integers in $$$a$$$ that $$$\mathrm{s.t. }\ p^k\mid\ a_i$$$, there exists $$$x\neq y$$$ $$$\mathrm{s.t.}\ p^k\nmid a_x$$$ $$$\mathrm{and}$$$ $$$p^k\nmid a_y$$$, so $$$p^k \nmid \textrm{lcm}(\{a_x,a_y\})$$$ and $$$p^k\ \nmid\ ans$$$. On the contrary, if there are at least $$$n-1$$$ integers in $$$a$$$ $$$\mathrm{s.t. }\ p^k\mid\ a_i$$$, between every two different $$$a_i$$$ there will be at least one multiple of $$$p^k$$$. So for every $$$(x,y)$$$, $$$p^k \mid \textrm{lcm}(\{a_x,a_y\})$$$. Therefore $$$p^k\ \mid\ ans$$$.
Solution 1. Define $$$d_i$$$ as a set that consists of all the numbers in $$$a$$$ except $$$a_i$$$. So $$$\gcd(d_i)$$$ is divisible by at least $$$n-1$$$ numbers in $$$a$$$. Also, if at least $$$n-1$$$ integers in $$$a$$$ $$$\mathrm{s.t. }\ p^k\ \mid\ a_i$$$, we can always find $$$i$$$ $$$\mathrm{s.t. }\ p^k \mid \gcd(d_i)$$$. According to the Observation, $$$ans=\textrm{lcm}(\{\gcd(d_1),\gcd(d_2),\gcd(d_3),...,\gcd(d_n)\})$$$.
Now consider how to calculate $$$\gcd(d_i)$$$. For every $$$i$$$, calculate $$$pre_i=\gcd(\{a_1,a_2,...,a_i\})$$$ and $$$suf_i=\gcd(\{a_{i},a_{i+1},...,a_n\})$$$. Therefore $$$\gcd(d_i)=\gcd(\{pre_{i-1},suf_{i+1}\})$$$ and we can get $$$pre$$$ and $$$suf$$$ in $$$O(n\cdot \log(v))$$$ time.
Time complexity: $$$O(n \log v)$$$
Solution 2. Enumerate every prime $$$\leq v$$$. For a prime $$$p$$$, enumerate every $$$a_i$$$ and calculate $$$k_i$$$ which stands for the maximum integer that $$$\mathrm{s.t. }\ p^{k_i} \mid a_i$$$. According to the Observation, the second smallest $$$k_i$$$ is the maximum integer $$$k$$$ that $$$\mathrm{s.t. }\ p^k \mid ans$$$. Now let's optimize this solution. If there has been at least two $$$a_i$$$ not divisible by $$$p$$$, then $$$p \nmid ans$$$, so just stop enumerate $$$a_i$$$.
Time complexity of the optimized solution is $$$O(v+n \log v)$$$ because every integer can be divided for at most $$$\log v $$$ times.