← 返回题目列表

Codeforces · 1016/G

G. 合适的团队

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

由于下赛季即将到来,您希望组建一支由两到三名参与者组成的团队。有 $$$n$$$ 个候选人,第 $$$i$$$ 个候选人的排名为 $$$a_i$$$。但是你对你的队友有奇怪的要求:如果你的排名是$$$v$$$并且选择了第$$$i$$$和第$$$j$$$个候选人,那么必须满足$$$GCD(v, a_i) = X$$$和$$$LCM(v, a_j) = Y$$$。

你非常有经验,所以你可以将你的排名更改为任何非负整数,但 $$$X$$$ 和 $$$Y$$$ 与你的出生日期相关,所以它们是固定的。

现在你想知道,有多少对 $$$(i, j)$$$ 使得存在满足以下约束的整数 $$$v$$$:$$$GCD(v, a_i) = X$$$ 和 $$$LCM(v, a_j) = Y$$$。有可能$$$i = j$$$ 并且你们组成了一个两人团队。

$$$GCD$$$ 是两个数字的最大公约数,$$$LCM$$$ — 最小公倍数。

输入

第一行包含三个整数 $$$n$$$、$$$X$$$ 和 $$$Y$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le X \le Y \le 10^{18}$$$) — 候选者的数量和相应的常量。

第二行包含 $$$n$$$ 空格分隔的整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$) — 候选人的排名。

输出

打印唯一的整数 - $$$(i, j)$$$ 对的数量,使得存在满足以下约束的整数 $$$v$$$:$$$GCD(v, a_i) = X$$$ 和 $$$LCM(v, a_j) = Y$$$。有可能 $$$i = j$$$。

示例

输入 #1

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

输出 #1

12

输入 #2

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

输出 #2

30

注意

在第一个示例中,接下来的对是有效的:$$$a_j = 1$$$ 和 $$$a_i = [2, 4, 6, 8, 10, 12]$$$ 或 $$$a_j = 2$$$ 和 $$$a_i = [2, 4, 6, 8, 10, 12]$$$。两种情况下的 $$$v$$$ 都可以等于 $$$2$$$。

在第二个示例中,接下来的对有效:

- $$$a_j = 1$$$ 且 $$$a_i = [1, 5, 7, 11]$$$;
- $$$a_j = 2$$$ 且 $$$a_i = [1, 5, 7, 11, 10, 8, 4, 2]$$$;
- $$$a_j = 3$$$ 且 $$$a_i = [1, 3, 5, 7, 9, 11]$$$;
- $$$a_j = 6$$$ 和 $$$a_i = [1, 3, 5, 7, 9, 11, 12, 10, 8, 6, 4, 2]$$$。