codeforces-scrape

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

1823C.md (3075B)


      1 Source: https://codeforces.com/problemset/problem/1823/C
      2 
      3 C. Strongly Composite
      4 
      5 time limit per test
      6 
      7 2 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 A prime number is an integer greater than $1$, which has exactly two divisors. For example, $7$ is a prime, since it has two divisors $\{1, 7\}$. A composite number is an integer greater than $1$, which has more than two different divisors.
     22 
     23 Note that the integer $1$ is neither prime nor composite.
     24 
     25 Let's look at some composite number $v$. It has several divisors: some divisors are prime, others are composite themselves. If the number of prime divisors of $v$ is less or equal to the number of composite divisors, let's name $v$ as strongly composite.
     26 
     27 For example, number $12$ has $6$ divisors: $\{1, 2, 3, 4, 6, 12\}$, two divisors $2$ and $3$ are prime, while three divisors $4$, $6$ and $12$ are composite. So, $12$ is strongly composite. Other examples of strongly composite numbers are $4$, $8$, $9$, $16$ and so on.
     28 
     29 On the other side, divisors of $15$ are $\{1, 3, 5, 15\}$: $3$ and $5$ are prime, $15$ is composite. So, $15$ is not a strongly composite. Other examples are: $2$, $3$, $5$, $6$, $7$, $10$ and so on.
     30 
     31 You are given $n$ integers $a_1, a_2, \dots, a_n$ ($a_i \gt 1$). You have to build an array $b_1, b_2, \dots, b_k$ such that following conditions are satisfied:
     32 
     33 * Product of all elements of array $a$ is equal to product of all elements of array $b$: $a_1 \cdot a_2 \cdot \ldots \cdot a_n = b_1 \cdot b_2 \cdot \ldots \cdot b_k$;
     34 * All elements of array $b$ are integers greater than $1$ and strongly composite;
     35 * The size $k$ of array $b$ is the maximum possible.
     36 
     37 Find the size $k$ of array $b$, or report, that there is no array $b$ satisfying the conditions.
     38 
     39 Input
     40 
     41 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.
     42 
     43 The first line of each test case contains one integer $n$ ($1 \le n \le 1000$) — the size of the array $a$.
     44 
     45 The second line of each test case contains $n$ integer $a_1, a_2, \dots a_n$ ($2 \le a_i \le 10^7$) — the array $a$ itself.
     46 
     47 It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.
     48 
     49 Output
     50 
     51 For each test case, print the size $k$ of array $b$, or $0$, if there is no array $b$ satisfying the conditions.
     52 
     53 Example
     54 
     55 Input
     56 
     57 ```
     58 8
     59 
     60 2
     61 
     62 3 6
     63 
     64 3
     65 
     66 3 4 5
     67 
     68 2
     69 
     70 2 3
     71 
     72 3
     73 
     74 3 10 14
     75 
     76 2
     77 
     78 25 30
     79 
     80 1
     81 
     82 1080
     83 
     84 9
     85 
     86 3 3 3 5 5 5 7 7 7
     87 
     88 20
     89 
     90 12 15 2 2 2 2 2 3 3 3 17 21 21 21 30 6 6 33 31 39
     91 ```
     92 
     93 Output
     94 
     95 ```
     96 1
     97 1
     98 0
     99 2
    100 2
    101 3
    102 4
    103 15
    104 ```
    105 
    106 Note
    107 
    108 In the first test case, we can get array $b = [18]$: $a_1 \cdot a_2 = 18 = b_1$; $18$ is strongly composite number.
    109 
    110 In the second test case, we can get array $b = [60]$: $a_1 \cdot a_2 \cdot a_3 = 60 = b_1$; $60$ is strongly composite number.
    111 
    112 In the third test case, there is no array $b$ satisfying the conditions.
    113 
    114 In the fourth test case, we can get array $b = [4, 105]$: $a_1 \cdot a_2 \cdot a_3 = 420 = b_1 \cdot b_2$; $4$ and $105$ are strongly composite numbers.