吐槽:太疯狂了,想使用unordered_map快一些结果超时了十几次!,反而用普通的map快速AC,查了发现unordered_map依赖于散列表,如果哈希函数映射的关键码出现的冲突过多,则最坏时间复杂度可以达到是O(n)。真的会有人卡umap(哭)
此题就是一个解方程题,把a[j]=x-a[i]带入a[i]*a[j]=y中可得,a * a-a * x+y=0。
利用一元二次方程求根公式代入可得a,可知a[i]与a[j]相等
所以只要求有多少个相等的a,然后排列组合一下就行
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5 + 10;
void solve() {
map<LL, LL> ma;//真的有人卡umap
LL n;
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
ma[x]++;
}
LL q;
cin >> q;
while (q--) {
LL x, y;
cin >> x >> y;
LL x1 = (sqrt(x * x - 4 * y)+x)/2;//求根
if (x1 * (x - x1) != y) cout << 0 << " ";//不满足韦达定理,无解
else if (x1 != x - x1) cout << ma[x1] * ma[x - x1] << " ";//有俩根的情况
else cout << ma[x1] * (ma[x1] - 1) / 2 << " ";
}
cout << "\n";
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}