题目描述

难度分:$1200$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(2 \leq n \leq 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 2n$)，数组元素互不相同。

输出有多少对$(i,j)$满足$i \lt j$且$a[i] \times a[j]=i+j$。

输入样例

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

输出样例

1
1
3

算法

试除法

由于数组$a$中的元素满足$a[i] \leq 2n$并不是很大，所以对于某个$a[i]=s$，可以在$O(\sqrt{n})$的时间复杂度下分解出两个不同的因子$d_1$和$d_2$，只要$d_1$和$d_2$都在数组$a$就凑出了一个数对。

先预处理出一个$id$数组，$id[a[i]]$表示$a[i]$在数组$a$中的索引$i$。然后枚举$s \in [1,2n]$，对$s$分解，计算$s$对答案的贡献即可。

复杂度分析

时间复杂度

遍历$s$的时间复杂度为$O(n)$，对$s$分解的时间复杂度为$O(\sqrt{n})$。因此，整个算法的时间复杂度为$O(n^{1.5})$。

空间复杂度

除了输入的数组$a$，空间消耗主要在于$id$数组，它是$O(n)$规模的，这也是整个算法的额外空间复杂度。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;
const int N = 200010;
int t, n, a[N], id[N<<1];

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 1; i <= n*2; i++) {
            id[i] = 0;
        }
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            id[a[i]] = i;
        }
        int ans = 0;
        for(int s = 1; s <= 2*n; s++) {
            for(int d1 = 1; d1 <= s/d1; d1++) {
                int d2 = s / d1;
                if(d1 < d2 && (id[d1] > 0 && id[d2] > 0) && d1*d2 == s && (id[d1] + id[d2] == s)) {
                    ans++;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}