题目描述

难度分:$983$

输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 2 \times 10^5)$。

问：有多少个下标三元组$(i,j,k)$满足$a[i] \times a[j]=a[k]$？

注意$i,j,k$之间没有大小约束。

输入样例$1$

3
6 2 3

输出样例$1$

2

输入样例$2$

1
2

输出样例$2$

0

输入样例$3$

10
1 3 2 4 6 8 2 2 3 7

输出样例$3$

62

算法

根号枚举+组合数学

由于$i,j,k$之间没有大小关系，我们可以先对$a$数组排序，然后遍历$k \in [1,n]$。由于$a[k] \leq 200000$，我们对每个$a[k]$也可以根号枚举其较小的那个因子$d$，然后得到另一个因子$\frac{a[k]}{d}$，在遍历的过程中维护一个哈希表$counter$，用来记录$[1,i]$中每个元素$a[j]$（$j \in [1,i]$）的频数。对每个$a[k]$（$k \in [1,n]$），把此时的候选三元组$(a[i]=d,a[j]=\frac{a[k]}{d},a[k])$放到一个集合$triples$中。

接下来我们遍历$triples$，看每个不同的三元组有多少种方案。对于满足$x \leq y \leq z$的三元组$(x,y,z)$，分为以下$4$种情况：

1. $x=y=z=1$，方案数就是$counter[x]^3$。
2. $x=y \lt z$，可以从$counter[x]$个$x$中选两个数充当$x$和$y$，方案数为$counter[x]^2 \times counter[z]$。
3. $x \lt y=z$，可以从$counter[y]$个$y$中选两个数充当$y$和$z$，同时$x$和$y$是可以交换的，因此方案数为$2 \times counter[x] \times counter[y]^2$。
4. $x \lt y \lt z$，$x$和$y$可以交换，方案数也是$2 \times counter[x] \times counter[y] \times counter[z]$。

以上所有三元组的方案都累加起来就是答案。

复杂度分析

时间复杂度

遍历$k \in [1,n]$时间复杂度为$O(n)$，枚举$a[k]$因子的时间复杂度为$O(\sqrt{N})$，因此根号枚举的时间复杂度为$O(n\sqrt{N})$，其中$N$是$a[i]$的值域。将候选三元组放入到集合中的时间复杂度可以是$O(1)$，但是在实现的时候由于不想写哈希函数直接用的有序集合，所以真实的时间复杂度会多一个$log$。

根据值域范围，每个$a[k]$的因子数不会很大，因此$triples$中的三元组数目大概就是一个常数比较大的$O(n)$，肯定是小于$O(n \sqrt{N})$。所以最后遍历三元组统计答案时，时间复杂度最大就是$O(n)$。

综上，整个算法的时间复杂度为$O(n\sqrt{N})$。

空间复杂度

哈希表$counter$中存了$O(n)$级别的键值对，空间复杂度为$O(n)$。三元组集合$triples$中存了$O(n)$级别的三元组，因此整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int n, a[N];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    if(n < 3) {
        puts("0");
        return 0;
    }
    sort(a + 1, a + n + 1);
    set<array<int, 3>> triples;
    unordered_map<int, long long> counter;
    for(int k = 1; k <= n; k++) {
        counter[a[k]]++;
        for(int d = 1; d <= a[k] / d; d++) {
            if(a[k] % d) continue;
            if(counter.count(d) && counter.count(a[k]/d)) {
                triples.insert({d, a[k]/d, a[k]});
            }
        }
    }
    long long ans = 0;
    for(auto t: triples) {
        int x = t[0], y = t[1], z = t[2];
        if(x == z) {
            // x=y=z
            long long cnt = counter[x];
            ans += cnt*cnt*cnt;
        }else if(x == y) {
            // x=y<z
            ans += counter[x]*counter[y]*counter[z];
        }else if(y == z) {
            // x<y=z
            ans += 2*counter[x]*counter[y]*counter[z];
        }else {
            // x<y<z
            ans += 2*counter[x]*counter[y]*counter[z];
        }
    }
    printf("%lld\n", ans);
    return 0;
}