问题 4880 --大象喜欢奇数序列

4880: 大象喜欢奇数序列

时间限制: 1 Sec  内存限制: 128 MB
提交: 86  解决: 36
[提交][状态][命题人:]

题目描述

    大象对奇数序列情有独钟。所谓奇数序列就是序列中的所有整数都是奇数。假设有n个正整数a1，a2，…，an构成的序列a，为了得到奇数序列，大象可以进行以下操作：选择任意偶数的值c，然后将序列a中所有等于c的数除以2。 例如，如果a=[6,8,12,6,3,12]，大象可以选择c=6，对数列完成操作后 a被转换成a=[3,8,12,3,3,12]。 现在，大象请聪明的您帮忙找到将a转换为一个奇数序列的最少操作次数(即序列中的每个元素都不能被2整除)。

输入

输入的第一行包含一个整数t，t为测试样例的数量(1≤t≤104)。 

每个样例的第一行包含一个整数n，为数组中的整数个数(1≤n≤2*105)。第二行包含该数组中的正整数a1, a2,…,ai,…,an (1≤ai≤109)。  

输出

对于每个样例，输出使测试用样例中的所有数字为奇数所需的最小操作次数。每个样例占一行。
样例输入
Copy
4
6
40 6 40 3 20 1
1
1024
4
2 4 8 16
3
3 1 7
样例输出
Copy
4
10
4
0

提示

请注意 

在本例的第一个测试用例中，最优操作顺序为:  

a=[40,6,40,3,20,1]; 

选择c = 6; 

现在=[40,3,40,3,20,1]; 

选择c = 40; 

现在=[20,3,20,3,20,1]; 

选择c = 20; 

现在= [10,3,10,3,10,1]; 

选择c = 10; 

现在a=[5,3,5,3,5,1] ，所有的数字都是奇数。 

因此，进行4次操作 后，所有数字都变成奇数。你不可能在3次或更少的操作下让它们都变成奇数。

来源

天梯赛#10C 

[提交][状态]