0 like 0 dislike
416 views
in Competitive-Programming by | 416 views

1 Answer

0 like 0 dislike

 

We will use the fact that each integer has a prime decomposition. We only need to consider prime numbers. We need to make sure that for any prime pp that any path with pp nodes containss at least one value that is divisible by pp. We will assign these nodes that are divisble by pp using a depth first search. We initialize all values as 1. If the distance from the root is a multiple of p/2p/2 we will multiply the value of that node by pp. We don’t do this for the root as otherwise it would become too large. The p/2p/2 is needed to take branches into account, see the sketch below as an example

p=3
        O-#
       /
O-O-#-O
       \
        O-#

The left node is the root. O is a root that is not multiplied by pp, # is a node that is. We notice that by spacing the depths by 3 we have accidentally created a path of length 3 that contains no multiples of pp. Using p/2p/2 as the depth interval solves this problem

by