← 返回题目列表

Codeforces · 1931/D

D. 可分割的对

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

Polycarp 有两个最喜欢的整数 $$$x$$$ 和 $$$y$$$(它们可以相等),并且他找到了一个长度为 $$$n$$$ 的数组 $$$a$$$。

Polycarp 认为一对索引 $$$\langle i, j \rangle$$$ ($$$1 \le i < j \le n$$$) 很漂亮,如果:

- $$$a_i + a_j$$$ 可以被 $$$x$$$ 整除;
- $$$a_i - a_j$$$ 可以被 $$$y$$$ 整除。

例如,如果 $$$x=5$$$、$$$y=2$$$、$$$n=6$$$、$$$a=$$$[$$$1, 2, 7, 4, 9, 6$$$],那么唯一漂亮的对是:

- $$$\langle 1, 5 \rangle$$$: $$$a_1 + a_5 = 1 + 9 = 10$$$ ($$$10$$$ 能被 $$$5$$$整除) 和 $$$a_1 - a_5 = 1 - 9 = -8$$$ ($$$-8$$$ 能被 $$$整除$$$2$$$);
- $$$\langle 4, 6 \rangle$$$: $$$a_4 + a_6 = 4 + 6 = 10$$$ ($$$10$$$ 能被 $$$5$$$整除) 和 $$$a_4 - a_6 = 4 - 6 = -2$$$ ($$$-2$$$ 能被 $$$整除$$$2$$$)。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$x$$$ 和 $$$y$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le x, y \le 10^9$$$) — 数组的大小和 Polycarp 最喜欢的整数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 数组 $$$a$$$ 中美丽对的数量。

示例

输入 #1

7
6 5 2
1 2 7 4 9 6
7 9 5
1 10 15 3 8 12 15
9 4 10
14 10 2 2 11 11 13 5 6
9 5 6
10 7 6 7 9 7 7 10 10
9 6 2
4 9 7 1 2 2 13 3 15
9 2 3
14 6 1 15 12 15 8 2 15
10 5 7
13 3 3 2 12 11 3 7 13 14

输出 #1

2
0
1
3
5
7
0