Appropriate Team
Contest: Educational Codeforces Round 48 (Rated for Div. 2)
Difficulty rating: 2700
Tags: bitmasks, math, number theory

Since next season are coming, you'd like to form a team from two or three participants. There are $$$n$$$ candidates, the $$$i$$$-th candidate has rank $$$a_i$$$. But you have weird requirements for your teammates: if you have rank $$$v$$$ and have chosen the $$$i$$$-th and $$$j$$$-th candidate, then $$$GCD(v, a_i) = X$$$ and $$$LCM(v, a_j) = Y$$$ must be met.

You are very experienced, so you can change your rank to any non-negative integer but $$$X$$$ and $$$Y$$$ are tied with your birthdate, so they are fixed.

Now you want to know, how many are there pairs $$$(i, j)$$$ such that there exists an integer $$$v$$$ meeting the following constraints: $$$GCD(v, a_i) = X$$$ and $$$LCM(v, a_j) = Y$$$. It's possible that $$$i = j$$$ and you form a team of two.

$$$GCD$$$ is the greatest common divisor of two number, $$$LCM$$$ — the least common multiple.

Input format:
First line contains three integers $$$n$$$, $$$X$$$ and $$$Y$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le X \le Y \le 10^{18}$$$) — the number of candidates and corresponding constants.

Second line contains $$$n$$$ space separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$) — ranks of candidates.

Output format:
Print the only integer — the number of pairs $$$(i, j)$$$ such that there exists an integer $$$v$$$ meeting the following constraints: $$$GCD(v, a_i) = X$$$ and $$$LCM(v, a_j) = Y$$$. It's possible that $$$i = j$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example next pairs are valid: $$$a_j = 1$$$ and $$$a_i = [2, 4, 6, 8, 10, 12]$$$ or $$$a_j = 2$$$ and $$$a_i = [2, 4, 6, 8, 10, 12]$$$. The $$$v$$$ in both cases can be equal to $$$2$$$.

In the second example next pairs are valid:

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

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

Example output:
12

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

Example output:
30

Editorial:
At first, $$$X \mid Y$$$ must be met (since $$$X \mid v$$$ and $$$v \mid Y$$$). Now let $$$Y = p_1^{py_1} p_2^{py_2} \dots p_z^{py_z}$$$ and $$$X = p_1^{px_1} p_2^{px_2} \dots p_z^{px_z}$$$. From now on let's consider only $$$p_k$$$ such that $$$px_k < py_k$$$.
Now let's look at $$$a_i$$$: $$$X \mid a_i$$$ must be met. Let $$$a_i = p_1^{pa_1} p_2^{pa_2} \dots p_l^{pa_l} \cdot a'$$$. Since $$$GCD(v, a_i) = X$$$, if $$$pa_k > px_k$$$ then $$$v$$$ must have $$$p_k$$$ to the power of $$$px_k$$$ in its factorization; otherwise power of $$$p_k$$$ can be any non-negative integer $$$\ge px_k$$$. It leads us to the bitmask of restrictions $$$min_i$$$ ($$$min_i[k] = (pa_k > px_k)$$$) with size equal to the number of different prime divisors of $$$Y$$$.
In the same way let's process $$$a_j$$$. Of course, $$$a_j \mid Y$$$ and if $$$pa_k < py_k$$$ then $$$v$$$ must have $$$p_k$$$ to the power of $$$py_k$$$ in its factorization. This is another restriction bitmask $$$max_j$$$ ($$$max_j[k] = (pa_k < py_k)$$$).
So, for any pair $$$(i, j)$$$ there exists $$$v$$$ if and only if $$$min_i\ \text{AND}\ max_j = 0$$$. Since we look only at $$$p_k$$$ where $$$px_k < py_k$$$ then $$$v$$$ can't have power of $$$p_k$$$ equal to $$$px_k$$$ and $$$py_k$$$ at the same time. For any other $$$p$$$ it is enough to have power of $$$p$$$ in $$$v$$$ equal to the power of $$$p$$$ in $$$Y$$$ (even if it's equal to $$$0$$$).
So, for each $$$max_j$$$ we need to know the number of $$$a_i$$$ such that $$$min_i$$$ is a submask of $$$\text{NOT}\ max_j$$$. So we just need to calculate sum of submasks for each mask; it can be done with $$$O(n\cdot 2^n)$$$ or $$$O(3^n)$$$.
Finally, how to factorize number $$$A$$$ up to $$$10^{18}$$$. Of course, Pollard algorithm helps, but there is another way, which works sometimes. Let's factorize $$$A$$$ with primes up to $$$10^6$$$. So after that if $$$A > 1$$$ there is only three cases: $$$A = p$$$, $$$A = p^2$$$ or $$$A = p \cdot q$$$. $$$A = p^2$$$ is easy to check ($$$\text{sqrtl}$$$ helps). Otherwise, just check $$$GCD$$$ with all $$$a_i$$$, $$$X$$$ and $$$Y$$$: if you have found $$$GCD \neq 1$$$ and $$$GCD \neq A$$$, then $$$A = p \cdot q$$$ and you have found $$$p$$$. Otherwise you can assume that $$$A = p$$$, because this probable mistake doesn't break anything in this task.
Result complexity is $$$O(A^{\frac{1}{3}} + n \log{A} + z \cdot 2^z)$$$ where $$$z$$$ is the number of prime divisors of $$$Y$$$ $$$(z \le 15)$$$.