Jellyfish and Green Apple
Contest: Codeforces Round 901 (Div. 2)
Difficulty rating: 1400
Tags: bitmasks, greedy, math, number theory

Jellyfish has $$$n$$$ green apple pieces. Each green apple piece weighs $$$1~\text{kg}$$$. Jellyfish wants to divide these green apple pieces equally among $$$m$$$ people.

Jellyfish has a magic knife. Each time Jellyfish can choose one piece of green apple and divide it into two smaller pieces, with each piece having half the weight of the original piece.

Jellyfish wants to know the minimum number of operations needed such that she can divide the green apple pieces such that the total weight of apple pieces received by each person is the same.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$). The description of the test cases follows.

The first and only line of each test case contains two integers, $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^9$$$) — the number of the green apple pieces initially and the number of the people.

Output format:
For each test case, output a single integer — the minimum number of operations required to divide all the green apples equally among the $$$m$$$ people. If this cannot be achieved using a finite number of operations, output $$$-1$$$ instead.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we do not need to divide the apple pieces. Each person will receive $$$2$$$ pieces of $$$1~\text{kg}$$$ and the total weight of apple pieces received by each person is $$$2~\text{kg}$$$.

In the second test case, it is impossible to divide the apple equally using a finite number of operations.

In the third test case, we can divide two of the apple pieces of weight $$$1~\text{kg}$$$, getting $$$4$$$ apple pieces of weight $$$0.5~\text{kg}$$$. Each person will receive $$$1$$$ apple piece of weight $$$0.5~\text{kg}$$$ and $$$2$$$ apple pieces of weight $$$1~\text{kg}$$$. The total weight of apple pieces received by each person is $$$2.5~\text{kg}$$$.

In the fourth test case, we first divide all $$$3$$$ of the apple pieces of weight $$$1~\text{kg}$$$, getting $$$6$$$ pieces of weight $$$0.5~\text{kg}$$$. Then, we further divide two of the apple pieces of weight $$$0.5~\text{kg}$$$, getting $$$4$$$ pieces of weight $$$0.25~\text{kg}$$$. Each person will receive $$$1$$$ apple piece of weight $$$0.5~\text{kg}$$$ and $$$1$$$ apple piece of weight $$$0.25~\text{kg}$$$. The total weight of apples received by each person is $$$0.75~\text{kg}$$$.

Example input:
4
10 5
1 5
10 4
3 4

Example output:
0
-1
2
5

Editorial:
Let's assume that the mass of each apple is $$$1$$$.
If $$$n \geq m$$$, we can make the problem transform $$$n < m$$$ by giving each person an apple at a time until there are not enough apples.
We can calculate the mass of apples that each person ends up with as $$$\frac n m$$$.
Since it's cut in half every time, if $$$\frac m {\gcd(n, m)}$$$ is not an integral power of $$$2$$$, there's no solution.
As the problem is transformed, $$$\frac n m$$$ is less than $$$1$$$, and $$$\frac m {\gcd(n, m)}$$$ is an integral power of $$$2$$$. So we can uniquely find a set of positive integers $$$S$$$ satisfying $$$\frac n m = \sum_{i \in S} \frac 1 {2^i}$$$. And this method can be proven to be optimal, if we find another multiset $$$T$$$ satisfying $$$S \neq T$$$, for every element $$$x$$$ that appears twice or more, We can make the answer better by removing two $$$x$$$ at a time from $$$T$$$ and adding one $$$x - 1$$$ to $$$T$$$. By repeating this process, eventually $$$T$$$ will become $$$S$$$.
So if we get $$$S$$$, we get the number of pieces of apple that each person ends up with. Each operation increases the number of pieces of apple by $$$1$$$. So the answer is $$$m \times |S| - n$$$.
Time complexity: $$$O(\log m)$$$ per test case.