多倍長整数の四則演算は桁数が大きいほど計算するのに時間がかかります。よって、桁数が大きい四則演算をする回数を減らせば時間を減らせるのではないかと考えます。

この問題を愚直に解くことを考えます。

\(i,j\) を全探索し、積が \(A_{k}\) と一致するような \(k\) が個数の総和をとる

この方針を C++ で boost の多倍長整数を用いて書くと以下のようになります。

#include <bits/stdc++.h>
using namespace std;
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;

int main(){
    using F = cpp_int;
    int N, ans = 0;
    cin >> N;
    vector<F> A(N);
    unordered_map<F, int> m;
    for(int i = 0; i < N; i++) cin >> A[i], m[A[i]]++;
    for(F a: A) for(F b: A){
        F tmp = a * b;
        if(m.count(tmp)) ans += m[tmp];
    }
    cout << ans << "\n";
}

この実装では TLE してしまいます。なぜなら桁数の大きい掛け算をたくさんの回数しているからです。

よって、桁数の大きい掛け算の回数を減らすことを考えます。

\(A\) がソートされていて、 \((i,j)\) の組が \(A_{i}\times A_{j} > A_{N}\) を満たしているとします。このとき、\(j < l\) を満たす \(l\) については \((i,l)\) に対する答えの探索をしなくて済みます。

この考察を用いて実装すると以下のようになります。

#include <bits/stdc++.h>
using namespace std;
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;

int main(){
    using F = cpp_int;
    int N, ans = 0;
    cin >> N;
    vector<F> A(N);
    unordered_map<F, int> m;
    for(int i = 0; i < N; i++) cin >> A[i], m[A[i]]++;
    sort(A.begin() , A.end()); // ソートしておく
    for(F a: A) for(F b: A){
        F tmp = a * b;
        if(tmp > A[N - 1]) break; // これ以上 j を増やす必要はない
        if(m.count(tmp)) ans += m[tmp];
    }
    cout << ans << "\n";
}

この実装は今回のテストケースでは AC を得ることができます。

この実装に対する最悪ケースとして \(N=1000,A_{1} = A_{2} =\cdots A_{N-1} = 10 ^{499}, A_{N} = 10^{998}\) が考えられますが、この入力に対して時間内に答えが出力できるか否かに関しては調べていません。

提出例 C++ 340ms

Python ではいつも通り多倍長整数を用いることができます。

Kiri8128 さんによる提出例 pypy 428ms

また、\(A\) がソートされているとき、 \(i\leq j\) の場合のみ調べれば答えを計算することができます。これを用いるとボトルネックとなる掛け算の回数を約半分にすることができます。

提出例 C++ 168ms

Kiri8128 さんによる提出例 pypy 263ms