Graph Connectivity With Threshold
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 == 0y % z == 0z > threshold
Given the two integers n and threshold, and an array of queries, determine for each queries[i] = [ai, bi] if cities ai and bi are connected directly or indirectly, meaning there is some path between them.
Return an array answer, where answer.length == queries.length and answer[i] is true if for the i^th query there is a path between ai and bi, or false if there is no path.
Example 1
Input
n = 6, threshold = 2, queries = [[1,4],[2,5],[3,6]]Output
[false,false,true]Using divisors strictly greater than 2, only cities 3 and 6 share a common divisor, so the query results are false, false, and true respectively.
Example 2
Input
n = 6, threshold = 0, queries = [[4,5],[3,4],[3,2],[2,6],[1,3]]Output
[true,true,true,true,true]Since the threshold is 0, all cities share divisor 1 and are connected to each other.
Constraints
- 2 <= n <= 10^4
- 0 <= threshold <= n
- 1 <= queries.length <= 10^5
- queries[i].length == 2
- 1 <= ai, bi <= cities
- ai != bi