「题解」二进制与一

传送门：水滴、洛谷

题目大意：给定一个正整数 $n$，给出操作次数 $p$。每次操作让 $n$ 加上一个非负整数 $x$，使得 $n$ 的第 $k$ 位为 $0$（从右往左数）。如果本身为 $1$ 就不用操作。且每次操作 $n + x$ 回影响后续操作。问 $x$ 的和是多少。

首先我们要知道，判断 $n$ 的第 $k$ 位是否为 $0$，就要用 $n$ 来与上 $1 << (k - 1)$ 来判断。如果为 $0$ 就过，否则就设 $x$ 为 $n % (1 << (k - 1))$，发现 $n$ 加上 $(1 << (k - 1)) - x$ 时，$n$ 的第 $k$ 位为 $1$，且 第 $k \sim 1$ 位都为 $0$，这种构造是最优的。

数据范围很大，要开 $long long$。

code

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ull unsigned long long
#define ll long long
using namespace std;

const int maxn = 1e5 + 5;

ll n, q, k, ans, x;

signed main() {
	scanf("%lld%lld", &n, &q);
	while (q--) {
		scanf("%lld", &k);
		if (!(n & (1ll << (k - 1)))) {
			x = n % (1ll << (k - 1));
			ans += (1ll << (k - 1)) - x;
			n += (1ll << (k - 1)) - x;
		}
	}
	printf("%lld", ans);
	return 0;
}