Number of special paths between two nodes

Question

Consider a directed graph. Each node in this graph has an integer label. We want to count the number of special paths between source and 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 source to 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.

2- value should become some predetermined integer k at the end of the path.

How many ways we can go from source to 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.

original problem statement

Answer 1

To start, notice that a room is only useful if v[i] divides k, where v[i] is the value of the room i. One other important thing to see is that, is the worst case there are at most 7 different primes (2*3*5*7*11*13) in the prime factorization of k and at most 19 primes total (2^19). This gives us a good hint that we can use a bitmask to represent the value of each node in such a way that lcm(v[i], v[j]) = v[i] | v[j] (bitwise or).

After having the graph pre-processed (with only the useful nodes and with the bitmask pre-computed for every node and for k), we can do DP on the graph that can be seen as a DAG because we will never go through the same node twice. Our state will then be (cur_node, cur_bitmask).

There's only one final detail for this to fit in memory. One should notice that for the second dimension of the DP is very sparse so we can use a map for each node to keep the DP results.

Hope my explanation was clear enough, if not, feel free to clarify your doubts :)

Sample implementation: http://pastebin.com/KLfyyvhv

Answer 2

I don't have a solution, but here's something that's probably needed for a solution.

Recall that every natural number can be written uniquely as a product of prime powers: $n = p_1^{k_1} p_2^{k_2} \dots p_a^{k_a}$ for a number $n$ with at most $a$ prime factors $p_1, \dots, p_a$ all unique.

The lcm of two numbers can be easily computed in terms of products of prime powers: You simply take the maximum exponent for every prime. If $n = p_1^{k_1} \dots p_a^{k_a}$ and $n' = p_1^{m_1} \dots p_a^{m_a}$, then $\mathit{lcm}(n, n') = p_1^{\mathrm{max}(k_1, m_1)} \dots p_a^{\mathrm{max}(k_a, m_a)}$.

It follows that if we go from node $u$ with value $b$ to node $v$ with key $b' = \mathit{lcm}(b, l[v])$ and $b' \ne b$, then $b' \ge 2 b$. Thus any special path from the source to the sink has length at most $\log_2 k$ (which for the programming contest, where $k \le 10^6$, means at most $20$ edges followed).