CF1857F Sum and Product

你有一个长度为 $n$ 的数组 $a$。 你的任务是回答 $q$ 个询问：给定 $x, y$，求有多少对 $i$ 和 $j$（$1 \le i < j \le n$）满足 $a_i + a_j = x$ 且 $a_i \cdot a_j = y$。 例如，对于数组 $[1,3,2]$，询问 $x=3, y=2$ 时，答案为 $1$： - $i=1$ 和 $j=2$ 不满足，因为 $1+3=4$ 不是 $3$，且 $1 \cdot 3=3$ 不是 $2$； - $i=1$ 和 $j=3$ 满足两个条件； - $i=2$ 和 $j=3$ 不满足，因为 $3+2=5$ 不是 $3$，且 $3 \cdot 2=6$ 不是 $2$。

第一行包含一个整数 $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$。

对于每个测试用例，输出一行包含 $q$ 个数字，分别表示每个询问的答案。

对于第一个测试用例，我们分别分析每一对数字： - 对 $(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)$；对于第三和第四个询问没有合适的对。在第二个测试用例中，所有的数对组合都是合适的。 由 ChatGPT 4.1 翻译