自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 22:53:00，当前版本为作者最后更新于2023-12-09 17:13:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

假设第 $i$ 个 A 类点和第 $j$ 个 B 类点会在第 $t$ 秒在 $(i,j)$ 相遇，则必须满足 $t\times a_i=j,t\times b_j=i$，故 $t=\dfrac{j}{a_i}=\dfrac{i}{b_j}$（这里暂且假设 $a_i,b_j$ 不为 $0$），再交叉相乘得到 $i\times a_i=j\times b_j$。

所以只需要在输入数组 $a$ 时记下所有 $i\times a_i$，然后在输入数组 $b$ 的时候看看有几个 $i$ 满足 $i\times a_i=j\times b_j$（有几个 $i$ 满足这个等式，就有几个 A 类点会和这个 B 类点相遇），最后再加到记录答案的变量 $s$ 上。

不要忘了特判 $a_i=0$ 和 $b_j=0$ 的情况，此时这个点原地不动，也不可能和其它点相遇。

#include<bits/stdc++.h>
using namespace std;
int a[1145141],b[1145141];
unordered_map<long long,int> ai;
int main(){
    ios::sync_with_stdio(false);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]!=0){
            long long temp=1ll*i*a[i];
            ai[temp]++;//ai[temp] 存的是满足 i*a_i=temp 的 i 的个数
        }
    }
    long long s=0;
    for(int j=1;j<=m;j++){
        cin>>b[j];
        if(b[j]!=0){
            long long temp=1ll*j*b[j];
            if(ai.count(temp)){//如果有 i 满足 i*a_i=j*b_j
                s+=ai[temp];//则将满足等式的 i 的个数加到答案中
            }
        }
    }
    cout<<s;
    return 0;
}