CF1857F.Sum and Product

You have an array $a$ of length $n$.

Your task is to answer $q$ queries: given $x,y$, find the number of pairs $i$ and $j$ ($1 \le i \lt j \le n$) that both $a_i + a_j = x$ and $a_i \cdot a_j = y$.

That is, for the array $[1,3,2]$ and asking for $x=3,y=2$ the answer is $1$:

• $i=1$ and $j=2$ fail because $1 + 3 = 4$ and not $3,$ also $1 \cdot 3=3$ and not $2$;
• $i=1$ and $j=3$ satisfies both conditions;
• $i=2$ and $j=3$ fail because $3 + 2 = 5$ and not $3,$ also $3 \cdot 2=6$ and not $2$;

你有一个长度为 $n$ 的数组 $a$。

你的任务是回答 $q$ 个查询：对于给定的 $x$ 和 $y$，找出满足 $1 \le i \lt j \le n$ 且同时满足 $a_i + a_j = x$ 与 $a_i \cdot a_j = y$ 的下标对 $(i, j)$ 的数量。

例如，对于数组 $[1,3,2]$ 以及查询 $x=3,\ y=2$，答案为 $1$：

• $i=1$ 与 $j=2$ 不满足条件，因为 $1 + 3 = 4 \ne 3$，且 $1 \cdot 3 = 3 \ne 2$；
• $i=1$ 与 $j=3$ 同时满足两个条件；
• $i=2$ 与 $j=3$ 不满足条件，因为 $3 + 2 = 5 \ne 3$，且 $3 \cdot 2 = 6 \ne 2$；

The first line contains one integer $t$ ($1\le t\le 10^4$) — the number of test cases.

The second line of each test case contains one integer $n$ ($1 \le n \le 2\cdot 10^5$) — the length of the array $a$.

The third line of each test case contains $n$ integers $a_1,a_2,\dots,a_n$ ($1 \le |a_i| \le 10^9$) — array $a$.

The fourth line of each test case contains the integer $q$ ($1 \le q \le 2\cdot 10^5$) — the number of requests.

The next $q$ lines contain two numbers each $x$ and $y$ ($1 \le |x|\le 2\cdot 10^9,1\le |y|\le 10^{18}$) — request.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$. This is also guaranteed for the sum of $q$ values.

第一行包含一个整数 $t$（$1\le t\le 10^4$）—— 测试用例的数量。

每个测试用例的第二行包含一个整数 $n$（$1 \le n \le 2\cdot 10^5$）—— 数组 $a$ 的长度。

每个测试用例的第三行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1 \le |a_i| \le 10^9$）—— 数组 $a$。

每个测试用例的第四行包含一个整数 $q$（$1 \le q \le 2\cdot 10^5$）—— 查询的数量。

接下来的 $q$ 行每行包含两个数 $x$ 和 $y$（$1 \le |x|\le 2\cdot 10^9,\,1\le |y|\le 10^{18}$）—— 一次查询。

保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$；同样地，所有测试用例的 $q$ 之和也不超过 $2\cdot 10^5$。

For each test case print a line with $q$ numbers — the answers to the queries.

对于每个测试用例，输出一行包含 $q$ 个数字——即各查询的答案。

For the first test case, let's analyze each pair of numbers separately:

• pair $(a_1,a_2)$: $a_1 + a_2 = 4$, $a_1 \cdot a_2 = 3$
• pair $(a_1,a_3)$: $a_1 + a_3 = 3$, $a_1 \cdot a_3 = 2$
• pair $(a_2,a_3)$: $a_2 + a_3 = 5$, $a_2 \cdot a_3 = 6$

From this, we can see that for the first query, the pair $(a_1,a_3)$ is suitable, for the second query, it is $(a_2,a_3)$, and there are no suitable pairs for the third and fourth queries.

In the second test case, all combinations of pairs are suitable.

对于第一个测试用例，我们分别分析每一对数字：

• 数对 $(a_1,a_2)$：$a_1 + a_2 = 4$，$a_1 \cdot a_2 = 3$
• 数对 $(a_1,a_3)$：$a_1 + a_3 = 3$，$a_1 \cdot a_3 = 2$
• 数对 $(a_2,a_3)$：$a_2 + a_3 = 5$，$a_2 \cdot a_3 = 6$

由此可知，对于第一个查询，合适的数对是 $(a_1,a_3)$；对于第二个查询，合适的数对是 $(a_2,a_3)$；而第三和第四个查询则没有合适的数对。

在第二个测试用例中，所有可能的数对组合均满足条件。