We have n cities labeled from 1 to n. Two different cities with labels x and y are directly connected by a bidirectional road if and only if x and y share a common divisor strictly greater than some threshold. More formally, cities with labels x and y have a road between them if there exists an integer z such that all of the following are true:
x % z == 0,y % z == 0, andz > threshold.Given the two integers, n and threshold, and an array of queries, you must determine for each queries[i] = [ai, bi] if cities ai and bi are connected (i.e. there is some path between them).
Return an array answer, where answer.length == queries.length and answer[i] is true if for the ith query, there is a path between ai and bi, or answer[i] is false if there is no path.
Example 1:
Input: n = 6, threshold = 2, queries = [[1,4],[2,5],[3,6]] Output: [false,false,true] Explanation: The divisors for each number: 1: 1 2: 1, 2 3: 1, 3 4: 1, 2, 4 5: 1, 5 6: 1, 2, 3, 6 Using the underlined divisors above the threshold, only cities 3 and 6 share a common divisor, so they are the only ones directly connected. The result of each query: [1,4] 1 is not connected to 4 [2,5] 2 is not connected to 5 [3,6] 3 is connected to 6 through path 3--6思路：这题需要借鉴：count primes的思路，就是i 跟i * j 需要union，剩下的就是 Union Find的模板；
class Solution { private class UnionFind { private int[] father; public UnionFind(int n) { this.father = new int[n + 1]; for(int i = 0; i <= n; i++) { father[i] = i; } } public int find(int x) { int j = x; while(father[j] != j) { j = father[j]; } // patch compression; while(x != j) { int fx = father[x]; father[x] = j; x = fx; } return j; } public void union(int a, int b) { int root_a = find(a); int root_b = find(b); if(root_a != root_b) { father[root_a] = root_b; } } } public List<Boolean> areConnected(int n, int threshold, int[][] queries) { UnionFind uf = new UnionFind(n); for(int i = threshold + 1; i <= n; i++) { for(int j = 2; j * i <= n; j++) { uf.union(i, j * i); } } List<Boolean> list = new ArrayList<>(); for(int[] query: queries) { list.add(uf.find(query[0]) == uf.find(query[1])); } return list; } }
