words, we repeatedly do the following: remove the last bit of our number, then choose to add or not to add n. adding n after removing i last bits can also be viewed as adding n*2i in the very beginning. assuming we do k steps in total, we can add n*2, n*4, ..., n*2k, and that means we can add n*m for any even number m between 0 and 2k+1-2.
after all the additions are done, we remove k last bits, and want to obtain the given number a. it means that before removing the k last bits, our number has to be between a*2k and (a+1)*2k-1.
which means that the problem 