Editorial for COCI '22 Contest 3 #4 Bomboni
Submitting an official solution before solving the problem yourself is a bannable offence.
This problem can be solved with dynamic programming. The easiest approach is to keep the product
in the current state, but the product can become really big. So the smarter approach is instead of the
product , keep
. Notice that a number
is divisible by
if and only if
. Notice the
following (the proof is left as an exercise to the reader):
So let us define as the number of paths starting at the upper left cell and ending at the cell
such that the greatest common divisor of the product of the numbers on the candy and
is equal to
.
Now it is easy to see the relation. We shall analyse the time complexity. Notice that all numbers smaller
than
have at most
divisors, which means at most
different values of
. So the
number of states is
which is enough with a constant relation.
Comments