Интересная проблема, и ваша интуиция искать кратные два и пять очень правильна!Количество конечных нулей равно меньшему из двух значений.Так, например, число конечных нулей в 124000 равно трем, потому что 124000 = 2^5 * 5^3 * 31, из этого мы берем 2^5 и 5^3, и min(5, 3) = 3.
Таким образом, проблема можетможно переформулировать как (я назову это P10 для дальнейшего использования):
P10:
Найдите минимальную кратность 2 или 5 в продуктеиз любых двух чисел в любых двух узлах в поддереве с корнем в данном узле.
Я подготовил пример с десятью числами:
Запишем числа в их факторизованной форме:
Хорошо!Мы обработали проблему в более работоспособную форму, теперь мы разберем ее на что-то более простое.
Во-первых, давайте сосредоточимся на аналогичной, упрощенной проблеме, без учета пятерок:
P2:
Найдите минимальную кратность 2 в произведении любых двух чисел в любых двух узлах в поддереве, укорененном в данном узле.
Теперь мызаботятся только о двойках, поэтому мы можем удалить все остальные факторы с картинки:
В этом дереве на каждом узле мы напишемдва младших числа из поддерева узла, идущие снизу вверх (как вы предложили!).При рассмотрении узла у нас уже будут два наименьших числа, определенных для всех его дочерних элементов, поэтому достаточно перебрать ближайшие дочерние элементы, чтобы найти два наименьших числа для узла:
Упрощенная задача решена!Просто умножьте числа в узле и верните экспоненту:
Теперь вышеприведенное на самом деле очень близко к решению реального вопроса ( P10 ).Повторите упрощенную версию с пятью вместо двух:
P5:
Найдите минимальную кратность 5 в произведении любых двух чисел в любых двух узлах в поддереве с корнем вданный узел.
Тогда для любого узла v решение для P10 равно P10 (v) = min (P2 (v),Р5 (v)) * * тысяча восемьдесят один.
Ресурсы: