A16684 | $Bitwise And Equals$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定一个整数数组 $a_1, a_2, \ldots, a_n$，还有一个整数 $X$。 你可以执行如下操作任意次（可以是零次）： - 选择一个 $i$，并将 $a_i$ 增加 $1$。 设 $a'$ 是最终状态下的数组。你的目标是用最少的操作次数使得 $a'_1\,\&\,a'_2\,\&\,\ldots\,\&\,a'_n = X$。其中 $\&$ 表示按位与运算。 有 $q$ 个查询整数 $X$：$X_1, X_2, \ldots, X_q$。请你对于每个 $X = X_i$ 求出答案。注意所有查询都是在相同的初始数组 $a$ 下独立进行。

第一行包含整数 $n$ 和 $q$（$2 \le n \le 200\,000$，$1 \le q \le 200\,000$）——数组长度与查询个数。 第二行包含整数 $a_1, a_2, \ldots, a_n$（对于每个 $i$，$0 \le a_i < 2^{20}$）。 接下来 $q$ 行，每行一个整数 $X_i$（$0 \le X_i < 2^{20}$）。

对于每个查询 $i$（共 $q$ 个），输出使数组 $a'$ 满足 $a'_1\,\&\,a'_2\,\&\,\ldots\,\&\,a'_n = X_i$ 所需的最小操作次数。 可以证明，总能在有限次数内得到满足条件的数组 $a'$。

输入 #1

输出 #1

C++ 编辑器

输入

输出