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.