自动搬运

查看原文

来自洛谷，原作者为

	ARIS2_0 路虽远，行则将至；事虽难，做则必成。

搬运于2025-08-24 23:09:28，当前版本为作者最后更新于2025-02-06 08:31:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

前言

赛时被小黄题创飞了，写个题解长长教训。

思路

设 $c_i$ 为 $a_j=i$ 的 $j$ 的个数，$d_i$ 为 $b_j=i$ 的 $j$ 的个数。

则对于一个数 $x$，它的最大出现次数为：

$$\sum_{i=1}^{10^9}\sum_{j=1}^{10^9}\min(c_i,d_j)[i\times j\bmod M=x] $$

注意到这里取 $\min$ 是正确的，因为 $a_i,b_i\le 10^9$ 且 $M=10^9+7$ 是质数，所以对于 $a_i\not=a_j$，不存在 $b_k$ 使得 $a_i\times b_k\equiv a_j\times b_k\pmod M$。

所以，如果有 $i\times j\bmod M=x$，那 $i$ 乘其他数、$j$ 乘其他数都不能得到 $x$，所以可以取 $\min$。

那么，我们枚举满足 $c_i\not=0$ 的 $i$ 与 $d_j\not=0$ 的 $i,j$，计算出 $x=i\times j\bmod M$，然后将 $ans_x$ 加上 $\min(c_i,d_j)$，最后计算 $ans$ 数组中的最大值就可以了。

$c,d,ans$ 数组需要用 unordered_map 实现，时间复杂度 $O(n^2)$，常数稍大。

Code

经过少许压行，马蜂不好还请见谅。

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
unordered_map<int,int>c,d,ans;
int main(){
	int n;cin>>n;
    for(int i=1,p;i<=n;i++)cin>>p,c[p]++;
    for(int i=1,p;i<=n;i++)cin>>p,d[p]++;
    for(pii i:c)for(pii j:d)ans[1ll*i.first*j.first%1000000007]+=min(i.second,j.second);
    int pos=0;for(pii i:ans)pos=max(pos,i.second);cout<<pos;
}