1744D.md (2376B)
1 Source: https://codeforces.com/problemset/problem/1744/D 2 3 D. Divisibility by 2^n 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 You are given an array of positive integers $a_1, a_2, \ldots, a_n$. 22 23 Make the product of all the numbers in the array (that is, $a_1 \cdot a_2 \cdot \ldots \cdot a_n$) divisible by $2^n$. 24 25 You can perform the following operation as many times as you like: 26 27 * select an arbitrary index $i$ ($1 \leq i \leq n$) and replace the value $a_i$ with $a_i=a_i \cdot i$. 28 29 You cannot apply the operation repeatedly to a single index. In other words, all selected values of $i$ must be different. 30 31 Find the smallest number of operations you need to perform to make the product of all the elements in the array divisible by $2^n$. Note that such a set of operations does not always exist. 32 33 Input 34 35 The first line of the input contains a single integer $t$ $(1 \leq t \leq 10^4$) — the number test cases. 36 37 Then the descriptions of the input data sets follow. 38 39 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of array $a$. 40 41 The second line of each test case contains exactly $n$ integers: $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$). 42 43 It is guaranteed that the sum of $n$ values over all test cases in a test does not exceed $2 \cdot 10^5$. 44 45 Output 46 47 For each test case, print the least number of operations to make the product of all numbers in the array divisible by $2^n$. If the answer does not exist, print -1. 48 49 Example 50 51 Input 52 53 ``` 54 6 55 56 1 57 58 2 59 60 2 61 62 3 2 63 64 3 65 66 10 6 11 67 68 4 69 70 13 17 1 1 71 72 5 73 74 1 1 12 1 1 75 76 6 77 78 20 7 14 18 3 5 79 ``` 80 81 Output 82 83 ``` 84 0 85 1 86 1 87 -1 88 2 89 1 90 ``` 91 92 Note 93 94 In the first test case, the product of all elements is initially $2$, so no operations needed. 95 96 In the second test case, the product of elements initially equals $6$. We can apply the operation for $i = 2$, and then $a_2$ becomes $2\cdot2=4$, and the product of numbers becomes $3\cdot4=12$, and this product of numbers is divided by $2^n=2^2=4$. 97 98 In the fourth test case, even if we apply all possible operations, we still cannot make the product of numbers divisible by $2^n$ — it will be $(13\cdot1)\cdot(17\cdot2)\cdot(1\cdot3)\cdot(1\cdot4)=5304$, which does not divide by $2^n=2^4=16$. 99 100 In the fifth test case, we can apply operations for $i = 2$ and $i = 4$.