A16492. Huge Pile
编程题
普及/提高-
知识点
题目描述
Andrei 有一大堆苹果，这一大堆苹果有 $n$ 个。他可以把这堆苹果分成两小堆：如果这堆苹果有 $x$ 个，那么他将把这一堆苹果分成 $\lfloor \frac{x}{2} \rfloor$ 个和 $\lceil \frac{x}{2} \rceil$ 个。这个分割过程需要花费 Andrei $1$ 分钟。
安德烈想吃 $k$ 个苹果，但他根本不想数他吃了多少苹果。因此，他想得到一堆正好有 $k$ 个苹果的苹果堆。请判断是否可以通过分堆来实现这一目标。如果可能，求安德烈得到一堆正好有 $k$ 个苹果所需的最短时间。
安德烈想吃 $k$ 个苹果，但他根本不想数他吃了多少苹果。因此，他想得到一堆正好有 $k$ 个苹果的苹果堆。请判断是否可以通过分堆来实现这一目标。如果可能，求安德烈得到一堆正好有 $k$ 个苹果所需的最短时间。
输入格式
每组数据由多个测试用例组成。
第一行包含一个整数 $t$ $(1 \le t \le 10^4)$ 表示测试用例数。下面 $t$ 行描述测试用例。
对于每个测试用例，输入一行两个整数 $n$ 和 $k$ 表示初始的一堆苹果的数量和 Andrei 希望吃的苹果数 $(1 \le n, k \le 10^9)$。
第一行包含一个整数 $t$ $(1 \le t \le 10^4)$ 表示测试用例数。下面 $t$ 行描述测试用例。
对于每个测试用例，输入一行两个整数 $n$ 和 $k$ 表示初始的一堆苹果的数量和 Andrei 希望吃的苹果数 $(1 \le n, k \le 10^9)$。
输出格式
对于每个测试用例，如果 Andrei 不可能获得恰好有 $k$
个苹果的苹果堆，输出 $−1$
。否则，输出获得这堆苹果所需的最短时间。
个苹果的苹果堆，输出 $−1$
。否则，输出获得这堆苹果所需的最短时间。
输入输出样例
输入 #1
4 10 3 11 5 21 4 1000000000 1
输出 #1
2 1 -1 29
说明/提示
在第一个测试案例中，第一次分割后会产生两堆苹果，每堆 $5$ 个。分割其中的一个，就会得到一个包含 $2$ 个苹果的苹果堆和一个包含 $3$ 个苹果的苹果堆，一共分割了两次，所以答案是 $2$ 。
在第二个测试案例中，第一次分割后会产生一个包含 $5$ 个苹果的苹果堆和一个包含 $6$ 个苹果的苹果堆，一共分割了一次，因此答案为 $1$ 。
在第三个测试案例中，只能得到有 $1$ 、 $2$ 、 $3$ 、 $5$ 、 $6$ 、 $10$ 、 $11$ 或 $21$ 个苹果的苹果堆，不可能得到含有 $4$ 个苹果的苹果堆，因此答案为 $-1$。
在第二个测试案例中，第一次分割后会产生一个包含 $5$ 个苹果的苹果堆和一个包含 $6$ 个苹果的苹果堆，一共分割了一次，因此答案为 $1$ 。
在第三个测试案例中，只能得到有 $1$ 、 $2$ 、 $3$ 、 $5$ 、 $6$ 、 $10$ 、 $11$ 或 $21$ 个苹果的苹果堆，不可能得到含有 $4$ 个苹果的苹果堆，因此答案为 $-1$。