U368054题解

zhujianheng · 2025-08-05 16:02:15 · 个人记录

题意概述：有一个 n 个数和一个 m 个数的序列 a_i，b_i，询问存不存在 a_i \times b_j=k，n，m \le 5 \times 10^5。

针对 50\% 的数据：n \le 3000,m \le 3000。

暴力（50pts）：

一看到 n \le 3000 和 m \le 3000，想到 O(nm) 的暴力算法，枚举每个 i 和 j，判断 a_i \times b_j 是否等于 k。

正解（100pts）：

看到 n \le 5 \times 10^5 和 m \le 5 \times 10^5，想到 O(n \log m) 的算法。枚举对象太多超时了怎么办？减少枚举对象。只枚举 i，询问 \dfrac{k}{a_i} 是否存在在 b 序列中。这个可以用 set 处理，时间复杂度是 O(\log m) 的。

当然，你也可以使用 map，时间复杂度也是 O(n \log m)。

目前暂时没数据，预计 8/10 就有了。

Code（不要抄代码）：

#include<bits/stdc++.h>
using namespace std;
const int N=500009;
set<int> s;
int a[N],b[N];
int main() {
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
        cin>>b[i],s.insert(b[i]);
    for(int i=1;i<=n;i++) {
        if(k%a[i]!=0) continue;
        int x=k/a[i];
        if(s.find(x)!=s.end()) {
            cout<<i<<" "<<*s.find(x);
            return 0;
        }
    }
    cout<<-1<<endl;
    return 0;
}

时间复杂度 O(n \log m)，足够通过本题。