Codeforces Round 891 (Div. 3) F. Sum and Product
思路:
对于x,y:ai+aj=x —> aj=x-ai
因此 ai*(x-ai) = y ——> ai = (x 土 sqr( x^2 - 4y ) ) /2
对应的 ai 就是要的两个值
若两个值不同 ans = ( cnt[a1] * cnt[a2] )
若相同 则ans = ( cnt[a1] * (cnt[a1]-1) )/2
#define int long long
#define ld long double
using namespace std;
int t;
void op()
{
int n, q, f;
cin >> n;
map<int, int>tmp;
for (int i = 1; i <= n; i++)
{
cin >> f;
tmp[f]++;
}
cin >> q;
for (int i = 0; i < q; i++)
{
int x, y;
cin >> x >> y;
int num = x * x - 4*y;
if (num < 0)cout << 0 << " ";
else
{
int sqr = sqrt(num);
if (sqr * sqr != num)cout << 0 << " ";
else
{
if (num == 0)cout << tmp[(x - sqr) / 2] * (tmp[(x - sqr) / 2] - 1) / 2 << " ";
else
{
int n1 = x - sqr, n2 = x + sqr;
cout << tmp[n1/2] * tmp[n2/2] << " ";
}
}
}
}
cout << endl;
}
signed main()
{
cin >> t;
while (t--)
{
op();
}
return 0;
}