Editorial for COCI '20 Contest 2 #3 Euklid
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