Official Analysis (C++)

Explanation

The first observation we need to make is that all spiders which share a common factor form a complete graph where all pairs of spiders in this group are friends with each other.

Thus, we can enumerate the prime factors of all spiders and keep track for each factor the spiders which divide it to store the edges in an efficient manner. Two spiders are friends iff they're both in some prime factor's list together.

However, doing a naive BFS from the starting node will take too long. To optimize this, we have to make another optimization, which is that it's always optimal to "use" a prime at most once in our path.

For example, take the path where the number of legs are $15$, $3$, and $9$ where we've used the common divisor $3$ two times. Here, we can cut out $3$ and move directly from $15$ to $9$.

This allows us to do an optimized BFS from the starting spider by keeping a global list of visited prime factors. For each spider, we iterate through its prime factors and see which ones haven't been used. If a factor hasn't been used, then it's standard BFS with backtracking.

Implementation

Time Complexity: $\mathcal{O}\left(n \left(\sqrt{A} + \log n\right)\right)$, where $A$ is the largest number of legs among the spiders.

Copy
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

/** @return n's prime factors */

Copy
import java.io.*;
import java.util.*;

public class FriendlySpiders {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int spiderNum = Integer.parseInt(read.readLine());

		Map<Integer, List<Integer>> trains = new HashMap<>();
		Set<Integer>[] primeFactors = new HashSet[spiderNum];