解题思路

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

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

2. 乘积的计算

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

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

3. 优化思路

由于题目中数据量非常大，直接暴力查找会超时。因此我们通过以下方法优化：

• 使用一个列表 ans 来预处理所有可能的乘积结果。这样，对于每次查询，就可以直接通过查询该列表获得结果，避免重复计算。
• 在预处理时，遍历每个唯一元素及其倍数，记录每个倍数的最小两个下标。

4. 查询处理

查询时，只需要直接查找预处理结果即可，时间复杂度为常数 $O(1)$。

复杂度分析

• 时间复杂度：

  • 对于预处理部分，遍历所有唯一元素及其倍数，时间复杂度大约是 $O(n \log n)$，其中 $n$ 是数组大小。由于我们对每个数的倍数进行处理，所以实际时间复杂度较低。
  • 对于查询部分，查询操作为常数时间 $O(1)$，因为我们通过预处理已经得到了所有可能的答案。

• 空间复杂度：

  • 使用了一个长度为 $10^6$ 的 ans 列表来存储每个可能的乘积结果，因此空间复杂度为 $O(10^6)$。

代码实现

Python 代码

n = int(input())  # 输入数组大小
a = list(map(int, input().split()))  # 输入数组元素

# 离散化：获取数组中出现的唯一元素，并记录每个数字最少的两个下标（1-indexed）
unique_vals = sorted(set(a))
indices = {}
for i, x in enumerate(a, start=1):
    if x not in indices:
        indices[x] = [i]
    else:
        if len(indices[x]) < 2:
            indices[x].append(i)

MAX_X = 1000000
# 注意：用列表生成式生成独立的子列表，避免使用 [[-1,-1]] * (MAX_X+1)（那样会产生浅拷贝）
ans = [[-1, -1] for _ in range(MAX_X + 1)]

# 利用调和级数思想预处理所有可能的乘积答案
# 对于每个唯一数字 u，在区间 [u, MAX_X] 内遍历所有 u 的倍数 m
# 设 m = u * k，则令 v = k。只有当 u >= v 且 v 在数组中存在时，才构成有效答案
for u in unique_vals:
    for m in range(u, MAX_X + 1, u):
        # 由于 m 为 u 的倍数，令 v = m // u
        v = m // u
        # 避免重复计算，只考虑 u >= v（若 u < v，则答案在之前已经计算）
        if u < v:
            break
        if v in indices:
            if u == v:
                # u == v 时需要该数字至少出现两次
                if len(indices[u]) >= 2:
                    i1, i2 = indices[u][0], indices[u][1]
                    ans[m] = [min(i1, i2), max(i1, i2)]
            else:
                i1 = indices[u][0]
                i2 = indices[v][0]
                ans[m] = [min(i1, i2), max(i1, i2)]

q = int(input())  # 输入查询次数
for _ in range(q):
    x = int(input())  # 输入每次查询的x值
    print(ans[x][0], ans[x][1])

Java 代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();  // 输入数组大小
        int[] a = new int[n];
        
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        // 离散化：记录每个数字的下标
        Map<Integer, List<Integer>> indices = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int x = a[i];
            if (!indices.containsKey(x)) {
                indices.put(x, new ArrayList<>());
            }
            indices.get(x).add(i + 1);  // 记录下标为1-indexed
        }

        int MAX_X = 1000000;
        int[][] ans = new int[MAX_X + 1][2];
        
        for (int i = 0; i <= MAX_X; i++) {
            ans[i][0] = ans[i][1] = -1;  // 初始化
        }

        // 预处理所有乘积结果
        for (int u : indices.keySet()) {
            for (int m = u; m <= MAX_X; m += u) {
                int v = m / u;
                if (u < v) break;
                if (indices.containsKey(v)) {
                    if (u == v && indices.get(u).size() >= 2) {
                        List<Integer> idx = indices.get(u);
                        ans[m][0] = Math.min(idx.get(0), idx.get(1));
                        ans[m][1] = Math.max(idx.get(0), idx.get(1));
                    } else if (u != v) {
                        List<Integer> idx_u = indices.get(u);
                        List<Integer> idx_v = indices.get(v);
                        ans[m][0] = Math.min(idx_u.get(0), idx_v.get(0));
                        ans[m][1] = Math.max(idx_u.get(0), idx_v.get(0));
                    }
                }
            }
        }

        int q = sc.nextInt();  // 输入查询次数
        for (int i = 0; i < q; i++) {
            int x = sc.nextInt();  // 输入每次查询的x值
            System.out.println(ans[x][0] + " " + ans[x][1]);
        }
        
        sc.close();
    }
}

C++ 代码

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    unordered_map<int, vector<int>> indices;
    for (int i = 0; i < n; i++) {
        indices[a[i]].push_back(i + 1);  // 记录下标为1-indexed
    }

    const int MAX_X = 1000000;
    vector<vector<int>> ans(MAX_X + 1, vector<int>(2, -1));
    
    // 预处理所有乘积结果
    for (const auto& pair : indices) {
        int u = pair.first;
        for (int m = u; m <= MAX_X; m += u) {
            int v = m / u;
            if (u < v) break;
            if (indices.find(v) != indices.end()) {
                if (u == v && indices[u].size() >= 2) {
                    ans[m][0] = min(indices[u][0], indices[u][1]);
                    ans[m][1] = max(indices[u][0], indices[u][1]);
                } else if (u != v) {
                    ans[m][0] = min(indices[u][0], indices[v][0]);
                    ans[m][1] = max(indices[u][0], indices[v][0]);
                }
            }
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        cout << ans[x][0] << " " << ans[x][1] << endl;
    }
    
    return 0;
}

题目内容

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

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

输入描述

第一行输入一个正整数$n$，代表数组的大小。

第二行输入$n$个正整数$a_i$，代表数组的元素。

第三行输入一个正整数$q$，代表询问次数。

接下来的$q$行，每行输入一个正整数$x$，代表一次询问。

$1≤n,q≤10^5$

$1≤a_i,x≤10^6$

输出描述

对于每次询问，如果无法找到两数乘积等于$x$，请输出$-1-1$。

否则输出和$j(i<j)$,用空格隔开，代表$a_i*a_j= x$。有多解时输出任意即可。

样例1

输入

5
1 2 3 2 4
2 
4 
5

输出

2 4
-1 -1

说明

第一组询问，输出$15$也是可以的。

第二组询问，显然无法找到两个元素相乘等于$5$。