## Editorial for Yet Another Contest 5 P4 - Nils++

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Josh

First, we can get a by calculating . This will be used in many other tasks.

Then, we simply note that the answer is .

Let . The main idea is that we will add to , creating . However, if , then we should clear to beforehand, such that our answer is .

So, we simply calculate . This value will be nonzero if and only if , so we can use this value in the CLR statement.

Note that variations of this trick allow us to affect the behaviour of the CLR statement depending on whether a value is negative, positive, non-negative or non-positive. This will be used in many other tasks.

First, we will solve the subtask where .

We can start by dealing with signs. Store the value of . If the result is , we should negate our final answer. Thus, we can deal with only non-negative values of and .

We will store the result in a variable , initially equal to . We will also create the number , and a counter , initially equal to . Then, we will perform steps.

In each step:

1. Increment by .
2. If is not positive, then increase by .

Now, we will deal with the harder variant of the task. We can use a very similar procedure. First, using repeated doubling, we can create the numbers . We can also create the numbers . Then, we perform steps, processing the powers of in decreasing order.

In each step:

1. Increment by the power of .
2. If is not positive, then increase by the relevant multiple of .

As a side note, if and are both equal to , we can't actually create any non-zero numbers (such as ). However, since we never create any non-zero numbers, we will still output the correct value of . This holds true in many other tasks, and explains the condition in the EQUALS task where at least one of and are non-zero.

Basically, we want to implement the Euclidean algorithm. We don't know how many steps it will take, so we will just perform the maximum number of steps needed for any pair (which turns out to be ). We want to implement the modulo operation, but if the number we are modulo-ing by is , we want to do nothing.

So, how do we do modulo? Well, modulo is basically just repeated subtraction whilst our current number is non-negative. We could do this naively, but we can borrow the same idea as for the harder variant of the PRODUCT task; we simply subtract numbers which are powers of 2 multiplied by the number we are modulo-ing by, whilst the current value is non-negative.

This task does not introduce any new ideas. We already know how to perform division and modulo from the GCD task. So it suffices to repeatedly divide and modulo both and by to get their corresponding bits, and then set the bit of answer if the corresponding bits are not equal. To check this, we can use our algorithm from the EQUALS task.

Process each prime number under in increasing order. First, we will decrease by the difference between the current prime and the previous prime, considering the prime preceding as . If is non-negative, then we will add to the answer.

In order to decrease by the difference efficiently, it suffices to precompute small integers. The largest prime gap under is , so we only need to precompute integers up to .