有 n 座城市，编号从 1 到 n 。编号为 x 和 y 的两座城市直接连通的前提是： x 和 y 的公因数中，至少有一个 严格大于 某个阈值 threshold 。更正式地说，如果存在整数 z ，且满足以下所有条件，则编号 x 和 y 的城市之间有一条道路：
x % z == 0 y % z == 0 z > threshold 给你两个整数 n 和 threshold ，以及一个待查询数组，请你判断每个查询 queries[i] = [ai, bi] 指向的城市 ai 和 bi 是否连通（即，它们之间是否存在一条路径）。
返回数组 answer ，其中answer.length == queries.length 。如果第 i 个查询中指向的城市 ai 和 bi 连通，则 answer[i] 为 true ；如果不连通，则 answer[i] 为 false 。
首先构造图，从每个公因数上考虑，将用该公因数的值对应的点放到一个集合中。
整个算法时间复杂度为 O(nlogn)
from typing import * class Solution: def __init__(self): self.arr = None def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]: self.arr = [i for i in range(n + 1)] for k in range(threshold + 1, n//2+1): i = 1 while (i + 1) * k <= n: self.set_union(i * k, (i + 1) * k) i += 1 return [self.find(query[0]) == self.find(query[1]) for query in queries] def set_union(self, i, j): find_i = self.find(i) find_j = self.find(j) if find_j != find_i: self.arr[find_j] = find_i def find(self, i): if i != self.arr[i]: self.arr[i] = self.find(self.arr[i]) return self.arr[i]
