CF1744D Divisibility

贪心

首先，看到 $1\le a_i\le 10^9$，我们暴力出奇迹的念头就已经消失了。但是我们能够发现，让乘积为 $2^n$ 的倍数就等同于所有数当中 $2$ 的因子的数量需要大于等于 $n$，而一个数 $2$ 的因子的数量很容易计算，因此我们就能很轻易地判断不执行任何操作能否满足条件。

然后就是贪心地去操作了。要想让在尽可能少的操作数量下 $2$ 的因子的数量尽可能的多，那么乘上的 $i$ 的 $2$ 的因子数量也要尽可能的多，因此我们只需要预处理出 $1\sim n$ 所有数的因子数量，然后从大到小排一个序，最后再贪心地选择即可。

import java.util.*
 
val cin = Scanner(System.`in`)
 
fun main() {
  for (t in 1..cin.nextInt()) {  // t 组数据
    val n = cin.nextInt()        // 元素数量
    var cnt = 0                  // 记录因子数量
    var ans = 0                  // 记录答案
    val a = IntArray(n + 1)      // 1—n 的因子数
    for (i in 1..n) {
      var x = cin.nextInt()
      while (x % 2 == 0) {       // 如果还有 2 的因子
        cnt++                    // 记录数量
        x /= 2                   // 去掉
      }
    }
    for (i in 1..n) {            // 预处理 1—n 的因子数
      var x = i
      while (x % 2 == 0) {       // 如果还有 2 的因子
        a[i - 1]++               // 记录数量
        x /= 2                   // 去掉
      }
    }
    a.sortDescending()           // 从大到小排序
    for (i in 0..<n) {           // 遍历前 n 个元素
      if (cnt >= n) {            // 已经满足要求
        break                    // 跳出循环
      }
      cnt += a[i]                // 计数器累加
      ans++                      // 记录答案
    }
    println(if (cnt >= n) ans else -1)
  }
}