思路

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$)，该复杂度过高，会导致超时，所以我们需要寻找更高效的算法。

2. 优化思路：问题转化

题目内容

给定由 $n$ 个整数构成的数组 {$a_1,a_2,...,a_n$} ，下标从 $1$ 到 $n$ 。现在有 $q$ 次查询，每次查询给出两个整数 $p,k$ 。

对于每个查询，定义如下过程：

从数组下标 $p$ 开始（包含该位置），依次向右扫描每个位置 $i(p≤i≤n)$；

统计满足 $gcd(a_p,a_i)≠1$ 的元素，当计数达到 $k$ 时，输出该位置的下标；

如果扫描结束仍未找到第 $k$ 个此类元素，则输出 $-1$ 。

最大公约数（$gcd$） 定义：多个整数共有约数中最大的一个，例如 $gcd(12,30)=6$ 。

输入描述

第一行输入两个整数 $n,q(2≤n,q≤6×10^4)$ ，分别表示数组长度和查询次数。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(2≤a_i≤6×10^4)$ ；

接下来 $q$ 行，每行输入两个整数 $p,k(1≤p≤n;1≤k≤n)$ 。

输出描述

对每次查询，新起一行输出一个整数，表示答案下标，若不存在，则输出 $-1$ .

样例1

输入

6 3
2 3 4 6 5 9
1 2
2 1
3 3

输出

3
2
-1

说明

查询 $(1,2)$ ：起始元素 $a_1=2$，扫描位置依次为 $1(gcd(2,2)=2≠1$，计数 $1$ )、$2(gcd(2,3)=1$，跳过)、$3(gcd(2,4)=2≠1$，计数 $2$ )，第 $2$ 个不互质元素下标 $3$ ；

查询 $(2,1)$ ：起始元素 $a_2=3$，扫描位置$2(gcd(3,3)=3≠1$ )，第 $1$ 个不互质元素下标 $2$ ；

查询 $(3,3)$ ：起始元素 $a_3=4$，扫描位置依次为 $3、4$ ，仅计数到 $2$ ，不存在第 $3$ 个，输出 $-1$ 。