Codeforces Round 875 (Div. 2)(D)

D （思维）

这个题意是给你两个数组，\(a\)和\(b\),我们需要找到这样的二元组\((i,j)\)满足\(a_i\times a_j=b_i+b_j\),问一共有多少组满足以上条件的二元组

题目还告诉我们数组里面的数字都是不大于\(n\)的，那么因为两个数相乘的范围一定是\(1-n\)的，那么我们可以枚举出较小的那一个\(a\)，然后再对其他的\(n\)个\(a\)和\(b\),那么已知三项，可以求出剩余的一项，就是和我们枚举的这个\(a\)所对应的\(b\),所以，我们也要记录当\(a\)为此时枚举的数字是对应的\(b\)的数量，可以用一个\(vector\)来存（用\(map\)可能会超时，正好数据范围也不大）

但是还有一个小细节的地方，就是我们需要保证\(a\)是有序的（这个解法是在知乎博主那里看到的）而且必须是从大到小的

题解

我后面自己试验了一下，如果不是有序的，那么最后获得的答案可能会少

假设此时的\(a1\)是\(1\)

后面有\((a,b) (1,1),(1,3) (3,2) (6,3)\)只有按照从小到大的顺序才可，其他的都是不对的

其中原因我也不是很清楚

这样的话，我们可以造成二元组的一定是\(a\)大于等于\(a1\)，\(a\)的乘积越来越大，对于同一个\(a\),\(b\)是递增的，那么我们所需的\(a2\)是在递减，但是感觉关系不大，还不是很懂为什么一定要排序

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
#include <bitset>
#include <numeric>
using namespace std;
#define int long long 
#define LL long long
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define eps 1e-10
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=1e6+10;
const int mod=1e9+7;
int tt;
int n;
pair<int,int>x[maxn];
void solve()
{
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>x[i].first;
  }
  for(int i=1;i<=n;i++)
  {
    cin>>x[i].second;
  }
  sort(x+1,x+1+n);
  int ans=0;
  for(int i=1;i*i<=n<<1;i++)
  {
    vector<int>cnt(n+1,0);
    int a1=i;
    for(int j=1;j<=n;j++)
    {
      int a2=x[j].first;
      int b2=x[j].second;
      int b1=a1*a2-b2;
      if(b1>=1&&b1<=n)
      {
        ans+=cnt[b1];
      }
      if(a1==a2)
      {
        cnt[b2]++;
      }
    }
  }
  cout<<ans<<"\n";
  return ;
}
signed main ()
{
  ios;
 // cin>>t;
  tt=1;
  cin>>tt;
  while (tt--)
  {
    solve();
  }
  system ("pause");
  return 0;
}