### James S. Plank

Sat Oct 8 12:36:33 EDT 2016

### The alternate graph

This sure feels like an unweighted shortest path (BFS) problem. However, like many Topcoder graph problems, you can't use the graph that they specify, but instead, you have to create an alternate graph.

Obviously, the graph that they specify is too big. If a[i] equals 2, and b[i] equals 3, and N equals 1,000,000,000, then there are roughly (500,000,000 * 333,333,333) edges. That's too big.

However, let's work on building a different graph that solves the problem, but is much smaller. Here's thought number one: If your path uses an edge (w,x) defined by (a[i],b[i]), then it will never take a subsequent edge (y,z) which is also defined by (a[i],b[i]). Why? Because the edge (w,z) will exist, and your path could have taken it instead of (w,x).

That observation helps us, because we can try to define our path as a sequence of (a[i],b[i]) values, rather than as a sequence of edges.

So, let's build a new graph. In this new graph, the nodes are i values (as in (a[i],b[i])). We'll have an edge from S to a node i if the (a[i],b[i]) includes node S as one of its a[i] nodes. And, we'll have an edge from a node i to T the (a[i],b[i]) includes node T as one of its b[i] nodes. Finally, we'll have an edge from node i to node j if there exists a city that is one of the b[i] nodes, and also one of the a[j] nodes.

The shortest path from S to T on this new graph defines a shortest path on the original graph. The path on the original graph will be one edge shorter than the path our our new graph (we'll see this on the example below).

We can find this shortest path using BFS, which is O(|V|+|E|). Our new graph has a maximum of 1000 nodes, so the maximum number of edges is 1,000,000. That's big, but well within topcoder limits.

### Converting the problem's graph to our alternate graph

First, how do we create the edges from S? Those will be to nodes i such that S is a multiple of a[i]. Similarly, the nodes to T will be the nodes i such that T is a multiple of b[i].

What about edges from node i to node j? We need to find a city C such that C is a multiple of b[i], and also a multiple of a[j]. In other words, we need to find the least common multiple (LCM) of b[i] and a[j]. If that value is less than or equal to N, then the edge exists. If it is greater to N, then the edge doesn't exist.

Is there a fast algorithm for LCM of x and y? Yes, and it is based on finding the greatest common denominator (GCD) of x and y? Suppose the GCD of x and y is z. Define s and t such that x = sz and y = tz. Then, the LCM of x and y is zst.

There is a fast algorithm (log time) for GCD. It is attributed to Euclid, and it goes as follows:

• Assume x is greater than y.
• Let a equal x % y.
• If a equals zero, then the GCD is y.
• Othewise, the GCD is equal to the GCD of y and a.
This gives you a way of creating the graph.

### Example 3

Example 3 is big enough to be interesting.
• S is 10, which is a multiple of 2, and 5. So, there are edges from S to nodes 0 and 1.
• T is 62, which is a multiple of 31. So, there is an edge from node 4 to T.
• Let's look at edges from node 0. b[0] is 25, so the only node whose a[i] value has an LCM with 25 that is less than 77 is node 1. So there is an edge from node 0 to node 1.
• Let's look at edges from node 1. b[1] is 7, so it will have edges to nodes 0, 2 and 3.
• Let's look at edges from node 2. b[2] is 11, so it will have edges to nodes 0, 1 and 3.
• Let's look at edges from node 3. b[3] is 13, so it will have edges to nodes 0, 1 and 5 (the LCM of 13 and 7 is 91, which is too big).
• Let's look at edges from node 4. b[4] is 31, so it will have an edge to node 0 (and of course to T).
• And let's look at edges from node 5. b[5] is 34, so it will have edges to nodes 0, 3 and 4.
That gives us the following graph:

You can see the shortest path in red - since it is composed of five edges, the answer is four.

Now that you know all of the pieces of the puzzle, go ahead and solve the problem!