\(A_i\) は \(1\) 以上 \(100\) 以下なので、\(A_i \times A_j \times A_k\) は \(1\) 以上 \(100^3 = 10^6\) 以下です。よって、\(1\) 以上 \(10^6\) 以下の全ての整数 \(n\) について、\(A_i \times A_j \times A_k = n\) かつ \(i \lt j \lt k\) を満たす \(i, j, k\) が存在するかを管理することで、この問題を \(O(N^3 + (\max A_i)^3)\) で解くことができます。

実装例 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<bool> x(1000001);
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            for (int k = j + 1; k < n; ++k) {
                x[a[i] * a[j] * a[k]] = true;
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= 1000000; ++i) {
        if (x[i]) {
            ans += 1;
        }
    }
    cout << ans << '\n';
    return 0;
}