思路

1. 暴力解法

   最直观的想法是严格按照题目描述进行模拟。对于每次查询 $(p, k)$，我们从下标 $p$ 开始遍历数组，逐个检查每个元素 $a_i$ 是否与 $a_p$ 的最大公约数不为 $1$。我们用一个计数器来记录满足条件的元素个数，当计数器达到 $k$ 时，就找到了答案。

   • 时间复杂度：对于每次查询，最坏情况下需要遍历 $O(n)$ 个元素。每次计算最大公约数（GCD）的时间复杂度约为 $O(\log V)$，其中 $V$ 是数组中的最大值。因此，总时间复杂度为 $O(q \cdot n \cdot \log V)$。
   • 可行性：根据题目给定的数据范围 ($n, q \leq 6 \times 10^4$)，该复杂度过高，会导致超时，所以我们需要寻找更高效的算法。