← 返回题目列表

Codeforces · 1857/F

F. 和与积

中文机器翻译题面 查看原题

你有一个长度为$$$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$$$ 值的总和也是有保证的。

输出

对于每个测试用例,打印一行包含 $$$q$$$ 数字 - 查询的答案。

示例

输入 #1

3
3
1 3 2
4
3 2
5 6
3 1
5 5
4
1 1 1 1
1
2 1
6
1 4 -2 3 3 3
3
2 -8
-1 -2
7 12

输出 #1

1 1 0 0 
6 
1 1 3

注意

对于第一个测试用例,让我们分别分析每对数字:

- 对 $$$(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$$$

在第二个测试用例中,所有对的组合都是合适的。