You are given an array A of first n natural numbers (1 to n). We say two numbers x and y are connected if gcd(x,y) >= t where t is some given threshold.

You are given query arrays source and destination of the same length. You need to find for every i, whether it is possible to reach from source[i] to destination[i] for the given constraints.

Example: n = 6 A = [1,2,3,4,5,6]
source = [1,2,2]
destination = [6,3,6]
threshold = 2

answer = [no,yes,yes]

Solution:

When we draw the graph, we have:
1 is not connected to anybody since threshold is 2.
6 is connected to 2 and 3 since gcd(6,3) = 3 and gcd(6,2) = 2.
So even 2 and 3 are connected indirectly.

Expected time complexity: As good as you can get. I would be glad to know as many approaches possible even if they have bad complexities.