Editorial for COCI '14 Contest 4 #1 Cesta
Submitting an official solution before solving the problem yourself is a bannable offence.
The prime factorization of number is
. Therefore,
is divisible by
if and only if it is divisible by
,
and
.
We know that a number is divisible by if its last digit is even and it's divisible by
when the sum of its digits is divisible by
and, naturally, we know that it's divisible by
when its last digit is either
or
. By combining these conditions, we conclude that
is divisible by
if and only if its last digit is
and the sum of its digits is divisible by
. Therefore, if the number from the input data doesn't contain the digit
or the sum of its digits is not divisible by
, we output
-1
.
What is obvious is that it is sufficient to sort the digits of number in descending order to get the required number.
Implementations with time complexity of or
, where
is the number of digits of
, were sufficient to score all points on this task.
Comments