Consider a directed graph. Each node in this graph has an integer label. We want to count the number of special paths between
sink. Let's define a variable named
value. Every path starts with
value = label[source]. When we move from node A to B value changes like this:
value = lcm( label[B], value ) where
lcm is lowest common multiplier. A speical path has two condition:
1- During the move from
sink value should always change. It means when moving from node A to B, if
value before and after the move remains unchanged, that path is not special.
value should become some predetermined integer
k at the end of the path.
How many ways we can go from
sink while not contradicting above conditions.
I think we can remove every node that
lcm(label[node], k) != k because this node could not be on any special path. Also condition one removes every loop from the graph.
Now the only algorithm I know about counting all the paths between two nodes is to use Dynamic Programming but I can't reduce this problem to that.
Also I can compute the result using backtrack but as there could be exponentially large number of such paths, it's not efficient enough.