题目内容

米小游拿到了一个数组，她有若干次询问，每次询问输入一个$x$，她希望你判断$x$能否由数组中的两个元素相乘得出。

用数学语言描述，你需要寻找到两个下标$i$和$j(i<j)$，满足$a_i*a_j=x$

解题思路

1. 离散化：记录每个数字的下标

首先，我们需要记录数组中每个数字出现的最少两个下标。这个可以通过字典来实现。因为题目要求输出的下标是 1-indexed，我们会记录每个数字的最小两个下标。

2. 乘积的计算

对于每个查询的数 $x$，我们需要判断是否存在两个数组中的元素，它们的乘积等于 $x$。我们可以利用因式分解的方式来进行查找。具体步骤是：

• 对于一个查询数 $x$，遍历它的所有因子（即 $x$ 的约数）。
• 对于每个因子 $u$，计算另一个因子 $v = x / u$。
• 如果数组中存在 $u$ 和 $v$，则可以通过这两个元素的乘积得到 $x$。