1349A.md (1591B)
1 Source: https://codeforces.com/problemset/problem/1349/A 2 3 A. Orac and LCM 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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: 22 23 * $\gcd(s)$ is the maximum positive integer $x$, such that all integers in $s$ are divisible on $x$. 24 * $\textrm{lcm}(s)$ is the minimum positive integer $x$, that divisible on all integers from $s$. 25 26 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$. 27 28 Orac has a sequence $a$ with length $n$. He come up with the multiset $t=\{\textrm{lcm}(\{a_i,a_j\})\ |\ i \lt 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. 29 30 Input 31 32 The first line contains one integer $n\ (2\le n\le 100\,000)$. 33 34 The second line contains $n$ integers, $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 200\,000$). 35 36 Output 37 38 Print one integer: $\gcd(\{\textrm{lcm}(\{a_i,a_j\})\ |\ i \lt j\})$. 39 40 Examples 41 42 Input 43 44 ``` 45 2 46 1 1 47 ``` 48 49 Output 50 51 ``` 52 1 53 ``` 54 55 Input 56 57 ``` 58 4 59 10 24 40 80 60 ``` 61 62 Output 63 64 ``` 65 40 66 ``` 67 68 Input 69 70 ``` 71 10 72 540 648 810 648 720 540 594 864 972 648 73 ``` 74 75 Output 76 77 ``` 78 54 79 ``` 80 81 Note 82 83 For the first example, $t=\{\textrm{lcm}(\{1,1\})\}=\{1\}$, so $\gcd(t)=1$. 84 85 For the second example, $t=\{120,40,80,120,240,80\}$, and it's not hard to see that $\gcd(t)=40$.