1875C.md (2522B)
1 Source: https://codeforces.com/problemset/problem/1875/C 2 3 C. Jellyfish and Green Apple 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 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. 24 25 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. 26 27 Input 28 29 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. 30 31 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. 32 33 Output 34 35 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. 36 37 Example 38 39 Input 40 41 ``` 42 4 43 44 10 5 45 46 1 5 47 48 10 4 49 50 3 4 51 ``` 52 53 Output 54 55 ``` 56 0 57 -1 58 2 59 5 60 ``` 61 62 Note 63 64 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}$. 65 66 In the second test case, it is impossible to divide the apple equally using a finite number of operations. 67 68 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}$. 69 70 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}$.