2203C.md (1708B)
1 Source: https://codeforces.com/problemset/problem/2203/C 2 3 C. Test Generator 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are developing a test generator. It takes two integers $s$ and $m$ as input. You need to construct an array of non-negative integers $a = [a_{1}, a_{2}, \dots, a_{n}]$ such that: 22 23 1. $\displaystyle\sum_{i=1}^{n} a_i = s$; 24 2. for each $i$, the condition $a_i \,\&\, m = a_i$ holds, where $\&$ denotes the bitwise AND operator. 25 26 In other words, in each number $a_i$, the bits that are set to one can only be in the positions where the bits in the number $m$ are also set to one. 27 28 Determine whether there exists at least one such array. If it exists, find the minimum possible length $n$. 29 30 Input 31 32 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 33 34 Each test case consists of a single line containing two integers $s$ and $m$ ($1 \le s, m \le 10^{18}$) — parameters of the generator. 35 36 Output 37 38 For each test case, print one integer: 39 40 * if such an array does not exist, print $-1$; 41 * otherwise, print the minimum possible value of $n$ — the length of the array. 42 43 Example 44 45 Input 46 47 ``` 48 6 49 50 13 5 51 52 13 3 53 54 13 6 55 56 1000000007 2776648 57 58 99999999999 1 59 60 998244353 1557287 61 ``` 62 63 Output 64 65 ``` 66 3 67 68 5 69 70 -1 71 72 -1 73 74 99999999999 75 76 642 77 ``` 78 79 Note 80 81 Let's analyze some examples: 82 83 * For $s = 13, m = 5$, the answer is $3$, as there is a suitable array $a = [5, 4, 4]$; 84 * For $s = 13, m = 3$, the answer is $5$, as there is a suitable array $a = [3, 3, 3, 3, 1]$; 85 * For $s = 13, m = 6$, the answer is $-1$, as there is no suitable array.