[Math][Codeforces] 1247C P Binary

P Binary:

My solution:

I was giving a virtual contest for this. The question before this one took 1 hour (ughh), and thus I couldn't solve this in time. So I solved this later.

So you're given a number $n$, which we need to check how many p-binary numbers are needed to make this $n$ number. 

What are you gonna do?

So basically let's say we have $n$ which we describe using $m$ p-binary numbers. That will look like:

$$ n = (2^{x_1}+p)+(2^{x_2}+p)+...+(2^{x_m}+p)$$

That can be made to look like:

$$ n = (\sum_{i=1}^{m} 2^{x_i})+m*p$$

That is equal to:

$$ n - m*p = (\sum_{i=1}^{m} 2^{x_i}) $$

We do not know the value of $m$ here. So,we can create an array with:

$$ n-i*p$$ where i goes from ${1,...,100}$, because you don't need more than that.

Now, check the number of set bits for each number in the array, starting from the left. Once you reach a point, where $\text{number of set bits} <= i$, you stop. As you can create $i$ such elements in the expansion given above, from a lesser number of bits. Just remember that you can create 2 elements from one set bit if the number is not 1. 

For example if you have a 2 (10), you can have two 1s (01). Similarly, you can see that you can the same for 4,8, et cetera. But you can't divide 1. So remember to check that $n-i*p>=i$, which means that the number can create $i$ elements. 

The logic here is that a number $j$ can, at max, be divided into $j$ elements.

It's a good question. 

Here's the code: