codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.