Test Generator

Research used: the official Codeforces problem page and the official Educational Codeforces Round 187 editorial/accepted solution at https://codeforces.com/blog/entry/151612. The statement here is still the canonical source.

The key is to stop trying to guess the array directly. That path gets messy fast, and the mess is fake.

Each valid number $a_i$ is a submask of $m$. For a fixed length $n$, look at one bit position $p$ where $m$ has a set bit. Across the whole array, this bit can appear in some number $c_p$ of elements. Since there are only $n$ elements,

$0 \le c_p \le n.$

The contribution of that bit to the total sum is $c_p2^p$, so the problem for a fixed $n$ becomes:

$s = \sum_{p: \text{bit }p\text{ is set in }m} c_p2^p, \qquad 0 \le c_p \le n.$

This is not just necessary, it is sufficient. If such counts exist, build the array by putting bit $p$ into the first $c_p$ elements. Every element still uses only bits from $m$, and the total contribution of bit $p$ is exactly $c_p2^p$.

So the answer is the minimum possible value of $\max c_p$ over all representations of $s$ using the allowed powers of two. Nice and clean. Annoyingly clean, even.

Now we need a feasibility check for a candidate $n$.

Think of every allowed bit $p$ of $m$ as a coin denomination $2^p$, and you have at most $n$ coins of each allowed denomination. Can you form exactly $s$?

Because all denominations are powers of two, greedily handling bigger denominations first is optimal. Scan bits from high to low and maintain need: the remaining unpaid prefix of $s$, measured in units of the current power of two.

Before processing bit $p$, suppose need is the unpaid amount from higher bits measured in units of $2^{p+1}$. Moving to bit $p$ doubles it, and then we add the actual bit of $s$:

$\text{need} \leftarrow 2\cdot \text{need} + [\text{bit }p\text{ of }s].$

Now need is how many units of $2^p$ must still be covered by denominations $2^p$ or smaller.

If bit $p$ is set in $m$, we may use up to $n$ coins of value $2^p$, so we do:

$\text{need} \leftarrow \text{need} - \min(\text{need}, n).$

If bit $p$ is not set in $m$, we cannot pay anything at this level, so all demand must be pushed down to smaller bits.

After processing bit $0$, there are no smaller positive denominations left. Therefore the candidate $n$ is feasible iff need == 0.

Why is the greedy step valid? At bit $p$, using a coin of value $2^p$ only reduces demand. It does not consume any smaller coins, and any unpaid $2^p$ unit would need to be replaced by smaller denominations later. So there is never a reason to save an available larger coin for later. This gives an induction: after every processed bit, greedy leaves the minimum possible unpaid demand among all choices using the processed denominations.

Feasibility is monotone: if length $n$ works, then any larger length also works, because every bit gets a larger count limit. So we binary search the minimum $n$.

Before binary searching, check whether a solution exists at all. Since $s \le 10^{18}$, using $n=s$ is always enough if any representation exists: if the smallest allowed denomination divides $s$, we could use that denomination repeatedly. The same feasibility check with limit $s$ catches all possible/impossible cases.

Edge cases:

• If $s$ is already a submask of $m$, the answer is $1$.
• If the lowest set bit of $m$ does not divide $s$, the answer is impossible; for example, with $m=6$, all allowed values are even, so $s=13$ is doomed.
• If $m=1$, each nonzero element can only contribute $1$, so the answer is exactly $s$.
• Values go up to $10^{18}$, so scan about $61$ bits and avoid tiny integer types. long long is fine for input, and using __int128 inside the check makes overflow a non-issue.

Complexity per test case is

$O(\log s \cdot \log s),$

because binary search takes about $60$ steps and each feasibility check scans about $61$ bits. With $10^4$ test cases, this is easily inside the limit.