3

There will be q queries to the problem. In each query, you will be given a random node in the whole tree. Each node of the tree stores some integer value. The solver needs to give the minimum number of zeroes trailing the product of any two numbers in any two nodes in the subtree rooted at the given node.

I thought of storing multiple of 2s and 5s in every node and calculate a minimum number of zeros for every node in a bottom-up manner.

4

1 回答 1

4

Interesting problem and your intuition to look for multiples of two and five is very correct! The number of trailing zeroes is equal to the lesser of the two values. So for example, the number of trailing zeroes in 124000 is three, because 124000 = 2^5 * 5^3 * 31, from this we take 2^5 and 5^3, and min(5, 3) = 3.

This way, the problem can be restated as (I'll call it P10 for further reference):

P10:

Find the minimum multiplicity of either 2 or 5 in the product of any two numbers in any two nodes in the subtree rooted at the given node.

I've prepared an example with ten numbers:

an example with ten numbers

Let's write the numbers in their factorized form:

numbers in their factorized form

Good! We have the problem processed into a more workable form, now we'll break it down into something simpler.

Firstly, let's focus on a similar, simplified problem, without considering fives:

P2:

Find the minimum multiplicity of 2 in the product of any two numbers in any two nodes in the subtree rooted at the given node.

Now we only care about twos, so we can remove all the other factors from the picture:

only twos

In this tree, on every node, we'll write the two lowest numbers from the node's subtree, going bottom-up (as you suggested!). When considering a node, we will already have the two lowest numbers determined for all of its children, so it's enough to iterate over the immediate children to find the two lowest numbers for a node:

two lowest numbers on every node

The simplified problem is solved! Just multiply the numbers in a node and return the exponent:

solution to the simplified problem

Now the above is actually very close to solving the real question (P10). Redo the simplified version with five instead of two:

P5:

Find the minimum multiplicity of 5 in the product of any two numbers in any two nodes in the subtree rooted at the given node.

Then, for any node v the solution to P10 is P10(v) = min(P2(v), P5(v)).

Resources:

于 2019-05-16T07:25:33.323 回答