Question

ABC339 F Product Equality

给出一个序列 \(A_1,A_2,\cdots,A_N\)

计算数对 \((i,j,k)\) 满足 \(A_i\times A_j= A_k\) 的个数

\(A_i \le 10^{1000}\)

Solution

思考 \(A_i\) 比较小的情况

如果 \(A_i \le 1e9\) 的，暴力枚举 \(i,j\) 然后用 \(map\) 查找 \(A_i\times A_j\) 的个数计数即可

考虑到模数 \(A\times B \% p = (A \% p) \times (B\% p) \%p\)

所以我们认为在相同模数下的乘积相同就相同

为了防止撞哈希值，使用双哈希就够了

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pii;
const int maxn = 1005;
const LL TT1 = 1e9 + 7, TT2 = 1e9 + 23;

map<pii,LL> mp;

pii read_pii(){
    pii x = make_pair(0,0); char ch = getchar();
    while(ch<'0' || ch>'9') ch = getchar();
    while(ch>='0' && ch<='9') { x.first = (x.first*10+ch-'0')%TT1; x.second = (x.second*10+ch-'0')%TT2; ch = getchar(); }
    return x;
}

int main(){
    freopen("F.in","r",stdin);
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++){
        pii p = read_pii();
        if(mp.find(p) == mp.end()) mp[p] = 1;
        else mp[p]++;
    }
    LL ans = 0;
    for(auto it1:mp){
        for(auto it2:mp){
            LL x1 = it1.first.first * it2.first.first, x2 = it1.first.second * it2.first.second;
            pii p = make_pair(x1%TT1,x2%TT2);
            auto it = mp.find(p);
            if(it != mp.end()) ans += it1.second * it2.second * it->second;
        }
    }
    printf("%lld\n",ans);
    return 0;
}