Editorial for COCI '20 Contest 4 #2 Vepar
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
For simplicity, replace the expression
with the equivalent
For each prime , define the map
which returns the largest power of
which divides
.
The left-hand side divides the right-hand side if an only if: for each , we have
of the left-hand side is at most the
of the right-hand side.
It's easy to see . We now want only
.
Proposition: We have
Proof: The first summand counts multiples of , the second counts multiples of
, and so on.
The solution is thus: find all primes up to , implement
, and check the relevant inequality of
for each prime.
Comments