離散の空間に道を検索する

最近トップコーダーの図表問題に苦しんでいます。The problem is to determine whether a "path" between two numbers exists, where a new number x is reachable from a start node s, if gcd(s,x)>k. It is clear that the first step from s is either a factor of s greater than k or a multiple of any such factor (less than or equal to the total number of nodes n).ｋより大きい因数を算出していますがｋより小さい因数を倍数と組み合わせる場合に新しい結節点がでるし前の点とのｇｃｄがｋより大きいことがありえそうです。
The initial approach of searching all multiples of all factors greater than k did not work, though, as, for 12345 and 54321 start and end with a k=1000 parameter, one can move 12345->2469*334->1002(divides 2469*334)->954906 (1002 times 953)->54321 (gcd with 954906 is 2859). This path would not be found, as 1002 is neither a factor of 12345 nor a multiple of a factor which is greater than k (it is a multiple of 3).
It seems that the only feasible algorithm is a tree search, which would cost O(n^3*sqrt(n)) it seems, as for each node all reachable nodes must be found (n^2), and reachability is checked via the gcd (sqrt(n)), and then all nodes must be visited on a backtracking search from the start to determine whether the goal is indirectly reachable. (lower bound O(n)). A more general approach of searching all multiples of all factors whereby the multiples exceed k also fails, as it leads to many false positives (e.g. if a large prime like 104279 is multiplied by a factor of 15 like 3 where k=4, the resulting multiple exceeds k, but gcd(3*104279,15)=3).
The only solution (from xiao_dan and dirak) seems to be to utilize dynamic programming, a recursive lookup mechanism or linked list, and equivalence classes. Basically, scan all values in [k+1,n] and for each x, form the equivalence class x, 2x, 3x, .... These will all have gcd of x among them and are connected. Add the class to the graph such that any values in the class which have already been added will cause their earlier classes to point to the new one. This makes sense, as 12 can be added once for 3, and then revisited for 4, 6, etc. In the case of 4, the 12 will cause the 3 class to point to 4. In the case of 6, this is a member of the 3 class already added, and thus cannot start its own class. While the correct solutions used a single array and recursion efficiently, the code is difficult to decipher. A more logical approach would likely be tu use two data structures: one for equivalence classes, and one for class translation (e.g. 3->4 in above case). Then, the algorithm should loop oveelr all equivalence classes in the k+1 to n range. Whenever a starting value i that has not been processed as another equivalence class is found, the value is saved and set as the cluster name for all multiples of this value (members of the equivalence class) and a link to any other classes that have multiples which lie in this new class also is added. Then, to determine the reachability of node x from node y, a lookup of the base class is performed. This lookup loops over the data structures of classes and class links until the classlink[x]=x relationship holds. If x and y have the same base class, x is reachable from y.
以外に難しい中級問題だった。