题解：CF2037B Intercepted Inputs

一道简单题，建议评红/橙 vp 时弱智操作导致交了好多发。

Description

原来一个矩阵的数以及长宽 n 和 m 被打乱到一个数列中，求原来的 n 与 m。

原题体面较为难懂，建议阅读原题题面 : https://codeforces.com/contest/2037/problem/B。

Solution

首先考虑什么情况下两个数合法。由于本身已经占了 2 个数，所以实际上，设第一个数为 x，第二个数为 y，则矩阵其他数数量为 xy，所以当 x 与 y 合法时，xy+2=n。

问题转化为有多少个双元组 (a_i,a_j) 满足 a_i\times a_j+2=n。我们可以想到开一个桶，对于 a_i，判断符合要求的 a_j 是否存在即可。

Code

请勿抄袭。

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int a[200005],f[200005];
int t,n;
void solve()
{
  memset(f,0,sizeof f);
        cin >> n;
        for (int i = 1;i <= n;i++)
        {
            cin >> a[i];
            f[a[i]]++;
        }
        n = n - 2;
        int ans1,ans2;
        for (int i = 1;i <= n + 2;i++)
        {
            if (n % a[i] == 0 && ((a[i] != n / a[i] && f[n / a[i]]) || (a[i] == n / a[i] && f[a[i]] > 1)))
            {
                ans1 = a[i],ans2 = n / a[i];
                break;
            }
        }
        cout << ans1 << ' ' << ans2 << endl;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}