{"problem":{"name":"[语言月赛 202401] 二进制与一","description":{"content":"给定一个正整数 $n$，以及操作次数 $q$。对于每次操作，给出一个正整数 $k$，要求：让 $n$ 加上一个非负整数 $x$，使得 $n$ 在二进制下的第 $k$ 位（从右往左数）是 $1$，并在符合要求的情况下，令 $x$ 最小。 请注意，每次操作都会让 $n$ 变为 $n + x$，会影响后续操作。 小山需要求出，所有的 $x$ 之和是多少。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB3919"},"statements":[{"statement_type":"Markdown","content":"给定一个正整数 $n$，以及操作次数 $q$。对于每次操作，给出一个正整数 $k$，要求：让 $n$ 加上一个非负整数 $x$，使得 $n$ 在二进制下的第 $k$ 位（从右往左数）是 $1$，并在符合要求的情况下，令 $x$ 最小。\n\n请注意，每次操作都会让 $n$ 变为 $n + x$，会影响后续操作。\n\n小山需要求出，所有的 $x$ 之和是多少。\n\n## Input\n\n输入共 $q + 1$ 行。\n\n第一行两个整数 $n$ 和 $q$。  \n接下来 $q$ 行，每行一个正整数 $k$，表示要让 $n$ 在二进制下从右往左数的第 $k$ 位是 $1$。\n\n## Output\n\n一行一个整数，表示所有的 $x$ 之和。\n\n[samples]\n\n## Note\n\n### 样例 1 说明\n$5$ 在二进制下是 $101$。\n\n- 对于第一次操作，需要让 $101$ 的第二位变为 $1$，则需让 $101$ 加上 $1$，变为 $110$；\n- 对于第二次操作，需要让 $110$ 的第三位是 $1$，由于 $110$ 的第三位本身就是一，所以无需改变；\n- 第三次操作同理，需要让 $110$ 加上 $2$。\n\n最终输出结果是 $1+0+2=3$。\n\n### 数据规模与约定\n\n对于 $100\\%$ 的数据，$1\\le n < 2^{32}，1\\le q\\le 10^5，1 \\le k\\le 32$。\n\n| 测试点编号 | $n$ | $q$ | $k$ |\n| :-: | :-: | :-: | :-: |\n| $1$ | $\\leq 4$ | $\\leq 10$ | $\\leq 2$ |\n| $2, 3$ | $\\leq 4$ | $\\leq 10$ | $\\leq 32$ |\n| $4, 5$ | $\\leq 1024$ | $\\leq 1000$ | $\\leq 10$ |\n| $6, 7$ | $< 2 ^ {32}$ | $\\leq 10$ | $\\leq 32$ |\n| $8 \\sim 10$ | $< 2 ^ {32}$ | $\\leq 10 ^ 5$ | $\\leq 32$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3919","tags":["2024","O2优化","位运算","循环结构","语言月赛"],"sample_group":[["5 3\n2\n3\n4\n","3\n"]],"created_at":"2026-03-03 11:09:25"}}