Anton buys a piglet#20

Anton buys a piglet (Editorial)

Problem Author:

Feysa Bohdan

Prepared by:

Feysa Bohdan

Tutorial by:

Pavlo Tsitsei

To determine if a sequence of operations exists: if is not divisible by , then the answer is , as there is no such sequence. Otherwise, it is always possible to create such a number. At a minimum, this can be done in \frac{x}{2^k} operations each time using the second button.

To find the sequence of these operations, a greedy algorithm can be used. Let's say we have already used the first button times and has bits. Then, to determine whether we need to add 2^k first or continue using the first button, we need to check the n-q-th bit of the number . If it is equal to 1, then before the operation, 2^k needs to be added. These actions need to be repeated until we get the number .