枚举 + 哈希

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

using namespace std;

typedef long long LL;

const int N = 7010, M = 2e5 + 10;;

int n;
int a[N], s[M];                             //s数组模拟哈希表

int main()
{
    int T;
    cin >> T;

    for (int t = 1; t <= T; t ++ )
    {
        int n;
        cin >> n;

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

        sort(a, a + n);
        memset(s, 0, sizeof s);

        LL res = 0;
        int not_zero = 0;                   //表示非0的个数
        for (int i = n - 1; i >= 0 && a[i] > 0; i -- )  //枚举Ay
        {
            not_zero ++ ;
            for (int j = 0; j < i; j ++ )               //枚举Ax
                if ((LL)a[i] * a[j] < M)
                    res += s[a[i] * a[j]];  //两个数的乘积在a中能找到对应的数
                                            //即：a[j] * a[i] = (a[j] * a[i])满足x < y < z
            s[a[i]] ++ ;                    //这一步思路有点像两数之和
        }

        int zero = n - not_zero;
        //组合数：从zero个0中选3个
        res += (LL)zero * (zero - 1) * (zero - 2) / 6;  //0 * 0 = 0

        //组合数：从zero个0中选两个，not_zero个非0中选一个
        res += (LL)not_zero * zero * (zero - 1) / 2;    //0 * A = 0

        printf("Case #%d: %lld\n", t, res);
    }

    return 0;
}