codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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}$.