题目翻译

$n$ 个大数 $a_i$，找三元组 $(i,j,k)$ 个数满足 $1\leq i,j,k\leq n$ 且 $a_i\times a_j=a_k$。

$n\leq 1000,a_i\leq \color{red}{10^{1000}}$。

题目思路

显然可以直接 FFT 高精度乘法。然后喜提 TLE，因为这个 $a_i$ 位数很长并且要跑很多轮乘法。

我们集中注意力，注意到满足 $a_i\times a_j=a_k$ 的必要条件是对于任意模数 $p$ 存在 $(a_i\bmod p)\times(a_j\bmod p)\equiv a_k \pmod p$。

所以我们多写几个模数判一下就好。高精度取模低精度可以一位一位扫过去。

时间复杂度是 $\mathcal O(n^2\log n)$，如果手写个 hash 可以做到 $\mathcal O(n^2)$。

本人组了 $8$ 个自己生日、同学生日和【数据删除】生日以及一些众所周知的大质数。

完整代码

AT submission 49960822

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P[] = {20091119,
                 11190119,
                 20102009,
                 998244353,
                 19260817,
                 1000000007,
                 998244853,
                 1145141};
map<vector<ll>, int> mp;
vector<ll> f(string &s)
{
    vector<ll> p;
    for (int i = 0; i < 8; i++)
        p.push_back(0);
    for (char c : s)
    {
        int d = c ^ '0';
        for (int i = 0; i < 8; i++)
            p[i] = (p[i] * 10 + d) % P[i];
    }
    return p;
}
int n;
int ans;
string s[1020];
vector<ll> v[1020];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        // vector<ll> a ;
        v[i] = f(s[i]);
        mp[v[i]]++;
        // for (int j : v[i])
        //     cout << j << " ";
        // cout << endl;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            vector<ll> a = v[i];
            vector<ll> b = v[j];
            for (int k = 0; k < 8; k++)
                a[k] = a[k] * b[k] % P[k];
            // for (int i : a)
            //     cout << i << " ";
            // cout << endl;
            ans += mp[a];
        }
    }
    cout << ans << endl;
    return 0;
}