Codeforces Round 641 (Div. 1) |
---|
Finished |
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:
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.
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$$$).
Print one integer: $$$\gcd(\{\textrm{lcm}(\{a_i,a_j\})\ |\ i<j\})$$$.
2 1 1
1
4 10 24 40 80
40
10 540 648 810 648 720 540 594 864 972 648
54
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$$$.
Name |
---|