CF1016G Appropriate Team

由于新赛季即将到来，你想从两名或三名参与者中组建一支队伍。有 $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$。

在第一个样例中，满足条件的配对有：$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]$。 由 ChatGPT 4.1 翻译