A16491. Unfair Game
编程题
普及+/提高
知识点
题目描述
Bob 厌倦了输给 Alice，为了保证自己不会再输，决定选择一个能确保自己获胜的游戏。Bob 从 $1$ 到 $n$ 中选了一个数，其中 $n = 2^d$，$d$ 是某个非负整数。起初，Alice 知道所选数字是否为偶数。
每一回合，Alice 可以选择将当前数字减半（只有当当前数字为偶数时可以执行），或者将当前数字减去 $1$。每次只有 Alice 执行操作。
操作后，Alice 会收到 Bob 的回复：要么是 $-1$，表示数字变为 $0$，Alice 获胜；要么是一个非负整数 $x$。如果当前的数字为 $a$，则 $x$ 满足以下条件：
1. $a$ 能被 $2^x$ 整除。
2. $a$ 不能被 $2^{x+1}$ 整除。
例如，若 $a=5$，则 $x=0$，因为 $5$ 能被 $2^0=1$ 整除但不能被 $2^1=2$ 整除；若 $a=12$，则 $x=2$，因为 $12$ 能被 $2^2=4$ 整除但不能被 $2^3=8$ 整除。
可以证明，对于任意 $a>0$，这样的 $x$ 存在且唯一。
Bob 仍然担心 Alice 会获胜，因此游戏最多只能进行 $k$ 步。此外，Bob 想让自己尽可能多地赢，所以他希望游戏数尽量多。给定 $n$ 和 $k$，请计算使得 Alice 无法在不超过 $k$ 步内必胜的初始数的数量（即在 $1$ 到 $n$ 中，有多少个数 Alice 最优策略下无法在 $k$ 步内赢得游戏）。
每一回合，Alice 可以选择将当前数字减半（只有当当前数字为偶数时可以执行），或者将当前数字减去 $1$。每次只有 Alice 执行操作。
操作后，Alice 会收到 Bob 的回复：要么是 $-1$，表示数字变为 $0$，Alice 获胜；要么是一个非负整数 $x$。如果当前的数字为 $a$，则 $x$ 满足以下条件：
1. $a$ 能被 $2^x$ 整除。
2. $a$ 不能被 $2^{x+1}$ 整除。
例如，若 $a=5$，则 $x=0$，因为 $5$ 能被 $2^0=1$ 整除但不能被 $2^1=2$ 整除；若 $a=12$，则 $x=2$，因为 $12$ 能被 $2^2=4$ 整除但不能被 $2^3=8$ 整除。
可以证明，对于任意 $a>0$，这样的 $x$ 存在且唯一。
Bob 仍然担心 Alice 会获胜，因此游戏最多只能进行 $k$ 步。此外，Bob 想让自己尽可能多地赢，所以他希望游戏数尽量多。给定 $n$ 和 $k$，请计算使得 Alice 无法在不超过 $k$ 步内必胜的初始数的数量（即在 $1$ 到 $n$ 中，有多少个数 Alice 最优策略下无法在 $k$ 步内赢得游戏）。
输入格式
第一行包含一个整数 $t$，表示测试用例数量，$1 \le t \le 10^4$。
每个测试用例包含一行，包含两个整数 $n$ 和 $k$，$1 \le n, k \le 10^9$，$n = 2^d$，$d$ 为某个非负整数。
每个测试用例包含一行，包含两个整数 $n$ 和 $k$，$1 \le n, k \le 10^9$，$n = 2^d$，$d$ 为某个非负整数。
输出格式
对于每个测试用例，输出一行一个整数，表示对于 $1$ 到 $n$，Alice 最优情况下无法在最多 $k$ 步内赢的初始数的数量。
输入输出样例
输入 #1
7 4 1 4 2 4 3 4 4 4 5 16 5 16 1
输出 #1
3 2 0 0 0 4 15
说明/提示
在第一个样例中，$a=2$、$a=3$、$a=4$ 满足条件，因为从 $a=1$ 一步可以变成 $0$，而对其它值可以证明最少需要 $2$ 步才行。
在第二个样例中，$a=3$ 和 $a=4$ 符合条件，因为对 $a=2$，Alice 可以通过 $2$ 步获胜。
在第三、四、五个样例中，没有符合条件的 $a$，因为对于 $a=3$ 和 $a=4$，Alice 至多三步内都能取胜。
在第二个样例中，$a=3$ 和 $a=4$ 符合条件，因为对 $a=2$，Alice 可以通过 $2$ 步获胜。
在第三、四、五个样例中，没有符合条件的 $a$，因为对于 $a=3$ 和 $a=4$，Alice 至多三步内都能取胜。