## Editorial for COCI '20 Contest 2 #3 Euklid

**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.**

The first few subtasks can be solved in many ways; e.g. for , the simplest way is . The fourth subtask is just calculating for ; we can check that this covers all .

For the large subtasks, the main issue is to find solutions not larger than .

Notice that, if the problem can be solved for the given constraints, it must have a solution where few division steps occur in executing Edicul's algorithm. More precisely, the product of the numbers on the sand is a nice monovariant, which decreases by a factor of in each step. Since up to the last step, there can be at most division steps for .

We can play with finitely many possibilities to find a construction similar to the following one. Let be a positive integer such that . Construction:

Notice that something small, such that divides . Also, we have .

It's easy to see . Let's prove that .

We have because . Hence, since .

However, , thus becomes after steps.

The time complexity is per test case.

## Comments