← 返回题目列表

Codeforces · 1225/C

C. p-二进制

中文机器翻译题面 查看原题

Vasya 会喜欢任何数字,只要它是 2 的整数幂。另一方面,Petya 非常保守,只喜欢单个整数 $$$p$$$(可以是正数、负数或零)。为了结合他们的口味,他们发明了 $$$p$$$ - 形式为 $$$2^x + p$$$ 的二进制数,其中 $$$x$$$ 是非负整数。

例如,某些 $$$-9$$$-二进制(“减九”二进制)数字为:$$$-8$$$(减八)、$$$7$$$ 和 $$$1015$$$($$$-8=2^0-9$$$、$$$7=2^4-9$$$、 $$$1015=2^{10}-9$$$)。

男孩们现在使用 $$$p$$$-二进制数字来表示一切。他们现在面临一个问题:给定一个正整数 $$$n$$$,他们需要将 $$$n$$$ 表示为总和的最小 $$$p$$$ 二进制数(不一定不同)是多少?代表可能是完全不可能的。帮助他们解决这个问题。

例如,如果 $$$p=0$$$ 我们可以将 $$$7$$$ 表示为 $$$2^0 + 2^1 + 2^2$$$。

如果 $$$p=-9$$$ 我们可以将 $$$7$$$ 表示为一个数字 $$$(2^4-9)$$$。

请注意,负的 $$$p$$$ 二进制数可以出现在总和中(参见注释部分的示例)。

输入

唯一的一行包含两个整数 $$$n$$$ 和 $$$p$$$ ($$$1 \leq n \leq 10^9$$$, $$$-1000 \leq p \leq 1000$$$)。

输出

如果无法将 $$$n$$$ 表示为任意数量的 $$$p$$$-二进制数的总和,则打印单个整数 $$$-1$$$。否则,打印尽可能少的被加数。

示例

输入 #1

24 0

输出 #1

2

输入 #2

24 1

输出 #2

3

输入 #3

24 -1

输出 #3

4

输入#4

4 -7

输出#4

2

输入 #5

1 1

输出 #5

-1

注意

$$$0$$$-二进制数只是常规的二进制幂,因此在第一个示例中我们可以表示 $$$24 = (2^4 + 0) + (2^3 + 0)$$$。

在第二个示例中,我们可以表示 $$$24 = (2^4 + 1) + (2^2 + 1) + (2^0 + 1)$$$。

在第三个示例中,我们可以表示 $$$24 = (2^4 - 1) + (2^2 - 1) + (2^2 - 1) + (2^2 - 1)$$$。请注意,允许重复加数。

在第四个示例中,我们可以表示 $$$4 = (2^4 - 7) + (2^1 - 7)$$$。请注意,第二个被加数为负数,这是允许的。

在第五个示例案例中,无法表示。