← 返回题目列表

Codeforces · 1349/A

A. Orac 和 LCM

中文机器翻译题面 查看原题

对于正整数多重集 $$$s=\{s_1,s_2,\dots,s_k\}$$$,定义 $$$s$$$ 的最大公约数 (GCD) 和最小公倍数 (LCM) 如下:

- $$$\gcd(s)$$$ 是最大正整数 $$$x$$$,使得 $$$s$$$ 中的所有整数都可以被 $$$x$$$ 整除。
- $$$\textrm{lcm}(s)$$$ 是最小正整数 $$$x$$$,可整除 $$$s$$$ 中的所有整数。

例如,$$$\gcd(\{8,12\})=4,\gcd(\{12,18,6\})=6$$$ 和 $$$\textrm{lcm}(\{4,6\})=12$$$。请注意,对于任何正整数 $$$x$$$,$$$\gcd(\{x\})=\textrm{lcm}(\{x\})=x$$$。

Orac 有一个序列 $$$a$$$,长度为 $$$n$$$。他提出了多重集 $$$t=\{\textrm{lcm}(\{a_i,a_j\})\ |\ i<j\}$$$,并要求你为他求 $$$\gcd(t)$$$ 的值。换句话说,您需要计算给定序列中所有元素对的 LCM 的 GCD。

输入

第一行包含一个整数 $$$n\ (2\le n\le 100\,000)$$$。

第二行包含 $$$n$$$ 整数,$$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 200\,000$$$)。

输出

打印一个整数:$$$\gcd(\{\textrm{lcm}(\{a_i,a_j\})\ |\ i<j\})$$$。

示例

输入 #1

2
1 1

输出 #1

1

输入 #2

4
10 24 40 80

输出 #2

40

输入 #3

10
540 648 810 648 720 540 594 864 972 648

输出 #3

54

注意

对于第一个示例,$$$t=\{\textrm{lcm}(\{1,1\})\}=\{1\}$$$,因此$$$\gcd(t)=1$$$。

对于第二个例子,$$$t=\{120,40,80,120,240,80\}$$$,不难看出$$$\gcd(t)=40$$$。