Divisibility by 2^n

题意翻译

### 题目描述 你被给予一个正整数数列 $ a_1, a_2, \ldots, a_n $ . 你需要让数列中所有数字的乘积 (也就是 $ a_1 \cdot a_2 \cdot \ldots \cdot a_n $ ) 能被 $ 2^n $ 整除. 你可以进行下列操作任意次: - 选择一个正整数 $ i $ ( $ 1 \leq i \leq n $ ) 然后把 $ a_i $ 替换为 $ a_i=a_i \cdot i $ . 你不能重复地对同一个 $ i $ 进行操作. 换句话说, 你选择的所有的 $ i $ 都必须不同. 你要找到让数列中所有数字的乘积能被 $ 2^n $ 整除的最少操作. 注意方案不一定存在. ### 输入格式 **本题有多组数据.** 输入的第一行只包含一个正整数 $ t $ $ (1 \leq t \leq 10^4 )$ — 测试数据的数目. 接下来 $ 2 \cdot t $ 行, 是 $ t $ 组数据. 每组数据的第一行只包含一个正整数 $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — 数列的长度 $ a $ . 每组数据的第二行包含 $ n $ 个正整数: $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^9 $ ). 保证所有测试数据中 $ n $ 的和不超过 $ 2 \cdot 10^5 $ . ### 输出格式 对每组数据, 输出让数列中所有数字的乘积能被 $ 2^n $ 整除的最少操作. 如果方案不存在，请输出$-1$. ### 提示 在第一个测试数据中, 数列中所有数字的乘积已经为 $ 2 $ , 因此不需要操作. 在第二个测试数据中, 数列中所有数字的乘积为 $ 6 $ . 我们可以对 $ i = 2 $ 进行操作, 于是 $ a_2 $ 变为 $ 2\cdot2=4 $ , 然后数列中所有数字的乘积为 $ 3\cdot4=12 $ , 这个数字能被 $ 2^n=2^2=4 $ 整除. 在第四个测试数据中, 就算我们执行所有可能的操作, 我们还是无法让数列中所有数字的乘积能被 $ 2^n $ 整除 — 结果为 $ (13\cdot1)\cdot(17\cdot2)\cdot(1\cdot3)\cdot(1\cdot4)=5304 $ , 不能被 $ 2^n=2^4=16 $ 整除. 在第五个测试数据中, 我们可以对 $ i = 2 $ 和 $ i = 4 $ 进行操作.

题目描述

You are given an array of positive integers $ a_1, a_2, \ldots, a_n $ . 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 $ . You can perform the following operation as many times as you like: - select an arbitrary index $ i $ ( $ 1 \leq i \leq n $ ) and replace the value $ a_i $ with $ a_i=a_i \cdot i $ . You cannot apply the operation repeatedly to a single index. In other words, all selected values of $ i $ must be different. 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.

输入输出格式

输入格式

The first line of the input contains a single integer $ t $ $ (1 \leq t \leq 10^4 $ ) — the number test cases. Then the descriptions of the input data sets follow. 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 $ . 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 $ ). It is guaranteed that the sum of $ n $ values over all test cases in a test does not exceed $ 2 \cdot 10^5 $ .

输出格式

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.

输入输出样例

输入样例 #1

6
1
2
2
3 2
3
10 6 11
4
13 17 1 1
5
1 1 12 1 1
6
20 7 14 18 3 5

输出样例 #1

0
1
1
-1
2
1

说明

In the first test case, the product of all elements is initially $ 2 $ , so no operations needed. 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 $ . 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 $ . In the fifth test case, we can apply operations for $ i = 2 $ and $ i = 4 $ .

**题意翻译**

### 题目描述

给定一个正整数数列 $ a_1, a_2, \ldots, a_n $.

你需要通过以下操作使得数列中所有数字的乘积（即 $ a_1 \cdot a_2 \cdot \ldots \cdot a_n $）能被 $ 2^n $ 整除：

- 选择一个正整数 $ i $（$ 1 \leq i \leq n $）然后将 $ a_i $ 替换为 $ a_i = a_i \cdot i $.

不能对同一个 $ i $ 重复进行操作。换句话说，你选择的所有的 $ i $ 都必须不同。

你要找到让数列中所有数字的乘积能被 $ 2^n $ 整除的最少操作次数。注意方案不一定存在。

### 输入格式

**本题有多组数据。**

输入的第一行只包含一个正整数 $ t $（$ 1 \leq t \leq 10^4 $）—— 测试数据的数目。

接下来 $ 2 \cdot t $ 行，是 $ t $ 组数据。

每组数据的第一行只包含一个正整数 $ n $（$ 1 \leq n \leq 2 \cdot 10^5 $）—— 数列的长度 $ a $。

每组数据的第二行包含 $ n $ 个正整数：$ a_1, a_2, \ldots, a_n $（$ 1 \leq a_i \leq 10^9 $）。

保证所有测试数据中 $ n $ 的和不超过 $ 2 \cdot 10^5 $。

### 输出格式

对每组数据，输出使数列中所有数字的乘积能被 $ 2^n $ 整除的最少操作次数。如果方案不存在，请输出 -1。

### 提示

在第一个测试数据中，数列中所有数字的乘积已经为 $ 2 $，因此不需要操作。

在第二个测试数据中，数列中所有数字的乘积为 $ 6 $。我们可以对 $ i = 2 $ 进行操作，于是 $ a_2 $ 变为 $ 2 \cdot 2 = 4 $，然后数列中所有数字的乘积为 $ 3 \cdot 4 = 12 $，这个数字能被 $ 2^n = 2^2 = 4 $ 整除。

在第四个测试数据中，就算我们执行所有可能的操作，我们还是无法让数列中所有数字的乘积能被 $ 2^n $ 整除——结果为 $ (13 \cdot 1) \cdot (17 \cdot 2) \cdot (1 \cdot 3) \cdot (1 \cdot 4) = 5304 $，不能被 $ 2^n = 2^4 = 16 $ 整除。

在第五个测试数据中，我们可以对 $ i = 2 $ 和 $ i = 4 $ 进行操作。

**题目描述**

给定一个正整数数组 $ a_1, a_2, \ldots, a_n $.

使数组中所有数字的乘积（即 $ a_1 \cdot a_2 \cdot \ldots \cdot a_n $）能被 $ 2^n $ 整除。

你可以进行任意次以下操作：

- 选择一个任意索引 $ i $（$ 1 \leq i \leq n $）并将 $ a_i $ 替换为 $ a_i = a_i \cdot i $.

你不能重复地对同一个索引进行操作。换句话说，所有选择的索引 $ i $ 必须不同。

找到你需要执行的最小操作次数，使数组中所有元素的乘积能被 $ 2^n $ 整除。注意这样的操作集并不总是存在。

**输入输出格式**

**输入格式**

输入的第一行包含一个正整数 $ t $（$ 1 \leq t \leq 10^4 $）—— 测试用例的数量。

然后是每个测试用例的描述。

每个测试用例的第一行包含一个正整数 $ n $（$ 1 \leq n \leq 2 \cdot 10^5 $）—— 数组 $ a $ 的长度。

每个测试用例的第二行包含 $ n $ 个整数：$ a_1, a_2, \ldots, a_n $（$ 1 \leq a_i \leq 10^9 $）。

保证所有测试用例中 $ n $ 的总和不超过 $ 2 \cdot 10^5 $。

**输出格式**

对于每个测试用例，打印使数组中所有数字的乘积能被 $ 2^n $ 整除的最少操作次数。如果答案不存在，打印 -**题意翻译** ### 题目描述 给定一个正整数数列 $ a_1, a_2, \ldots, a_n $. 你需要通过以下操作使得数列中所有数字的乘积（即 $ a_1 \cdot a_2 \cdot \ldots \cdot a_n $）能被 $ 2^n $ 整除： - 选择一个正整数 $ i $（$ 1 \leq i \leq n $）然后将 $ a_i $ 替换为 $ a_i = a_i \cdot i $. 不能对同一个 $ i $ 重复进行操作。换句话说，你选择的所有的 $ i $ 都必须不同。 你要找到让数列中所有数字的乘积能被 $ 2^n $ 整除的最少操作次数。注意方案不一定存在。 ### 输入格式 **本题有多组数据。** 输入的第一行只包含一个正整数 $ t $（$ 1 \leq t \leq 10^4 $）—— 测试数据的数目。 接下来 $ 2 \cdot t $ 行，是 $ t $ 组数据。 每组数据的第一行只包含一个正整数 $ n $（$ 1 \leq n \leq 2 \cdot 10^5 $）—— 数列的长度 $ a $。 每组数据的第二行包含 $ n $ 个正整数：$ a_1, a_2, \ldots, a_n $（$ 1 \leq a_i \leq 10^9 $）。 保证所有测试数据中 $ n $ 的和不超过 $ 2 \cdot 10^5 $。 ### 输出格式 对每组数据，输出使数列中所有数字的乘积能被 $ 2^n $ 整除的最少操作次数。如果方案不存在，请输出 -1。 ### 提示 在第一个测试数据中，数列中所有数字的乘积已经为 $ 2 $，因此不需要操作。 在第二个测试数据中，数列中所有数字的乘积为 $ 6 $。我们可以对 $ i = 2 $ 进行操作，于是 $ a_2 $ 变为 $ 2 \cdot 2 = 4 $，然后数列中所有数字的乘积为 $ 3 \cdot 4 = 12 $，这个数字能被 $ 2^n = 2^2 = 4 $ 整除。 在第四个测试数据中，就算我们执行所有可能的操作，我们还是无法让数列中所有数字的乘积能被 $ 2^n $ 整除——结果为 $ (13 \cdot 1) \cdot (17 \cdot 2) \cdot (1 \cdot 3) \cdot (1 \cdot 4) = 5304 $，不能被 $ 2^n = 2^4 = 16 $ 整除。 在第五个测试数据中，我们可以对 $ i = 2 $ 和 $ i = 4 $ 进行操作。 **题目描述** 给定一个正整数数组 $ a_1, a_2, \ldots, a_n $. 使数组中所有数字的乘积（即 $ a_1 \cdot a_2 \cdot \ldots \cdot a_n $）能被 $ 2^n $ 整除。 你可以进行任意次以下操作： - 选择一个任意索引 $ i $（$ 1 \leq i \leq n $）并将 $ a_i $ 替换为 $ a_i = a_i \cdot i $. 你不能重复地对同一个索引进行操作。换句话说，所有选择的索引 $ i $ 必须不同。 找到你需要执行的最小操作次数，使数组中所有元素的乘积能被 $ 2^n $ 整除。注意这样的操作集并不总是存在。 **输入输出格式** **输入格式** 输入的第一行包含一个正整数 $ t $（$ 1 \leq t \leq 10^4 $）—— 测试用例的数量。 然后是每个测试用例的描述。 每个测试用例的第一行包含一个正整数 $ n $（$ 1 \leq n \leq 2 \cdot 10^5 $）—— 数组 $ a $ 的长度。 每个测试用例的第二行包含 $ n $ 个整数：$ a_1, a_2, \ldots, a_n $（$ 1 \leq a_i \leq 10^9 $）。 保证所有测试用例中 $ n $ 的总和不超过 $ 2 \cdot 10^5 $。 **输出格式** 对于每个测试用例，打印使数组中所有数字的乘积能被 $ 2^n $ 整除的最少操作次数。如果答案不存在，打印 -