A6459. 二进制与一
编程题
入门
知识点
题目描述
给定一个正整数 $n$，以及操作次数 $q$。对于每次操作，给出一个正整数 $k$，要求：让 $n$ 加上一个非负整数 $x$，使得 $n$ 在二进制下的第 $k$ 位（从右往左数）是 $1$，并在符合要求的情况下，令 $x$ 最小。 请注意，每次操作都会让 $n$ 变为 $n + x$，会影响后续操作。 小山需要求出，所有的 $x$ 之和是多少。
输入格式
输入共 $q + 1$ 行。 第一行两个整数 $n$ 和 $q$。 接下来 $q$ 行，每行一个正整数 $k$，表示要让 $n$ 在二进制下从右往左数的第 $k$ 位是 $1$。
输出格式
一行一个整数，表示所有的 $x$ 之和。
输入输出样例
输入 #1
5 3 2 3 4
输出 #1
3
说明/提示
## 样例 1
说明 $5$ 在二进制下是 $101$。
- 对于第一次操作，需要让 $101$ 的第二位变为 $1$，则需让 $101$ 加上 $1$，变为 $110$；
- 对于第二次操作，需要让 $110$ 的第三位是 $1$，由于 $110$ 的第三位本身就是一，所以无需改变；
- 第三次操作同理，需要让 $110$ 加上 $2$。
最终输出结果是 $1+0+2=3$。
## 数据规模与约定
对于 $100\%$ 的数据，$1\le n < 2^{32}，1\le q\le 10^5，1 \le k\le 32$。
说明 $5$ 在二进制下是 $101$。
- 对于第一次操作，需要让 $101$ 的第二位变为 $1$，则需让 $101$ 加上 $1$，变为 $110$；
- 对于第二次操作，需要让 $110$ 的第三位是 $1$，由于 $110$ 的第三位本身就是一，所以无需改变；
- 第三次操作同理，需要让 $110$ 加上 $2$。
最终输出结果是 $1+0+2=3$。
## 数据规模与约定
对于 $100\%$ 的数据，$1\le n < 2^{32}，1\le q\le 10^5，1 \le k\le 32$。