A12928. p-binary
编程题
普及/提高-
知识点
题目描述
Vasya will fancy any number as long as it is an integer power of two. Petya, on the other hand, is very conservative and only likes a single integer $p$ (which may be positive, negative, or zero). To combine their tastes, they invented $p$ -binary numbers of the form $2^x + p$ , where $x$ is a non-negative integer.
For example, some $-9$ -binary ("minus nine" binary) numbers are: $-8$ (minus eight), $7$ and $1015$ ( $-8=2^0-9$ , $7=2^4-9$ , $1015=2^{10}-9$ ).
The boys now use $p$ -binary numbers to represent everything. They now face a problem: given a positive integer $n$ , what's the smallest number of $p$ -binary numbers (not necessarily distinct) they need to represent $n$ as their sum? It may be possible that representation is impossible altogether. Help them solve this problem.
For example, if $p=0$ we can represent $7$ as $2^0 + 2^1 + 2^2$ .
And if $p=-9$ we can represent $7$ as one number $(2^4-9)$ .
Note that negative $p$ -binary numbers are allowed to be in the sum (see the Notes section for an example).
For example, some $-9$ -binary ("minus nine" binary) numbers are: $-8$ (minus eight), $7$ and $1015$ ( $-8=2^0-9$ , $7=2^4-9$ , $1015=2^{10}-9$ ).
The boys now use $p$ -binary numbers to represent everything. They now face a problem: given a positive integer $n$ , what's the smallest number of $p$ -binary numbers (not necessarily distinct) they need to represent $n$ as their sum? It may be possible that representation is impossible altogether. Help them solve this problem.
For example, if $p=0$ we can represent $7$ as $2^0 + 2^1 + 2^2$ .
And if $p=-9$ we can represent $7$ as one number $(2^4-9)$ .
Note that negative $p$ -binary numbers are allowed to be in the sum (see the Notes section for an example).
输入格式
The only line contains two integers $n$ and $p$ ( $1 \leq n \leq 10^9$ , $-1000 \leq p \leq 1000$ ).
输出格式
If it is impossible to represent $n$ as the sum of any number of $p$ -binary numbers, print a single integer $-1$ . Otherwise, print the smallest possible number of summands.
输入输出样例
输入 #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$ -binary numbers are just regular binary powers, thus in the first sample case we can represent $24 = (2^4 + 0) + (2^3 + 0)$ .
In the second sample case, we can represent $24 = (2^4 + 1) + (2^2 + 1) + (2^0 + 1)$ .
In the third sample case, we can represent $24 = (2^4 - 1) + (2^2 - 1) + (2^2 - 1) + (2^2 - 1)$ . Note that repeated summands are allowed.
In the fourth sample case, we can represent $4 = (2^4 - 7) + (2^1 - 7)$ . Note that the second summand is negative, which is allowed.
In the fifth sample case, no representation is possible.
In the second sample case, we can represent $24 = (2^4 + 1) + (2^2 + 1) + (2^0 + 1)$ .
In the third sample case, we can represent $24 = (2^4 - 1) + (2^2 - 1) + (2^2 - 1) + (2^2 - 1)$ . Note that repeated summands are allowed.
In the fourth sample case, we can represent $4 = (2^4 - 7) + (2^1 - 7)$ . Note that the second summand is negative, which is allowed.
In the fifth sample case, no representation is possible.