题解：P11682 [Algo Beat Contest 001 D] Dreamed Sequence
ARIS2_0
·
·
题解
前言
赛时被小黄题创飞了，写个题解长长教训。
思路
设 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 数组中的最大值就可以了。
### Code
经过少许压行，马蜂不好还请见谅。
```cpp
#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;
}
```