#D. 神奇的2^n整除

    传统题 文件IO:div 1000ms 256MiB

神奇的2^n整除

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述:

给定一个n个数的数组,为了使得所有元素相乘能够被2的n次方整除。 你可以选择如下方法

选择一个位置ai乘以它的下标i(1<=i<=n)。ai = ai*i

每个i只能乘一次。 找到这个需要乘的最小个数。

输入格式:

第一行一个整数t,表示有t组数据(1<=t<=10^4)

接下来每组测试数据

第一行一个正整数n表示数组元素个数(1<=n<=2*10^5)

第二行n个正整数ai。(1<=ai<=10^9)

输出格式:

一个最小数,使得所有元素乘积能被2^n整除,如果不能输出-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
0
1
1
-1
2
1

提示

对于第二组数据 2 3 2 两个元素,要使得3 * 2被2^2整除 还需要让2 * 2 所以需要乘一个i=2. 所以结果为1

O(t*nlogn)可AC

10.22模拟赛

未参加
状态
已结束
规则
OI
题目
4
开始于
2022-10-21 17:30
结束于
2022-12-2 9:30
持续时间
1000 小时
主持人
参赛人数
35