【题解】乘积三元组

题意

有三个长度为的序列，从三个中各选一个元素相乘等于的组合有多少种。

题解

三重循环的暴力来找的话复杂度为是肯定超时的。那我们可以这样先暴力记录下两个序列各选一个元素相乘的结果，然后我们遍历序列，去之前处理的结果中去找有多少个的值加入到答案中即可。

复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int a[N];
int b[N];
int c[N];
map<long long,long long>vis;
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(int i=0;i<n;i++)
        scanf("%d",&b[i]);
    for(int i=0;i<n;i++)
        scanf("%d",&c[i]);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            vis[a[i]*b[j]]++;
    int ans=0;
    for(int i=0;i<n;i++)
        if(k%c[i]==0)
            ans+=vis[k/c[i]];
    printf("%d\n",ans);
}