English · Original
Chinese · Translation
Formal · Original
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
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
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$.
[samples]
## 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]$.
由于下个赛季即将到来，你希望从两名或三名选手中组队。共有 $n$ 名候选人，第 $i$ 名候选人的排名为 $a_i$。但你对队友有奇怪的要求：如果你的排名为 $v$，并选择了第 $i$ 和第 $j$ 名候选人，则必须满足 $G C D (v, a_i) = X$ 且 $L C M (v, a_j) = Y$。
你非常有经验，可以将你的排名改为任意非负整数，但 $X$ 和 $Y$ 与你的生日绑定，因此是固定的。
现在你想知道，有多少对 $(i, j)$ 满足存在一个整数 $v$，使得以下条件成立：$G C D (v, a_i) = X$ 且 $L C M (v, a_j) = Y$。允许 $i = j$，即你可以组成两人队伍。
$G C D$ 表示两个数的最大公约数，$L C M$ 表示最小公倍数。
第一行包含三个整数 $n$、$X$ 和 $Y$（$1 lt.eq n lt.eq 2 dot.op 10^5$，$1 lt.eq X lt.eq Y lt.eq 10^(18)$）——候选人数及对应常数。
第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, dots.h, a_n$（$1 lt.eq a_i lt.eq 10^(18)$）——候选人的排名。
请输出一个整数——满足存在整数 $v$ 使得 $G C D (v, a_i) = X$ 且 $L C M (v, a_j) = Y$ 的对 $(i, j)$ 的数量。允许 $i = j$。
## Input
第一行包含三个整数 $n$、$X$ 和 $Y$（$1 lt.eq n lt.eq 2 dot.op 10^5$，$1 lt.eq X lt.eq Y lt.eq 10^(18)$）——候选人数及对应常数。第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, dots.h, a_n$（$1 lt.eq a_i lt.eq 10^(18)$）——候选人的排名。
## Output
请输出一个整数——满足存在整数 $v$ 使得 $G C D (v, a_i) = X$ 且 $L C M (v, a_j) = Y$ 的对 $(i, j)$ 的数量。允许 $i = j$。
[samples]
## Note
在第一个例子中，以下对是有效的：$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 ]$。
**Definitions**
Let $ n \in \mathbb{Z}^+ $, $ X, Y \in \mathbb{Z}^+ $ with $ 1 \le X \le Y $.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers, where $ a_i \in \mathbb{Z}^+ $ for all $ i \in \{1, \dots, n\} $.
**Constraints**
1. $ 1 \le n \le 2 \cdot 10^5 $
2. $ 1 \le X \le Y \le 10^{18} $
3. $ 1 \le a_i \le 10^{18} $ for all $ i \in \{1, \dots, n\} $
**Objective**
Count the number of ordered pairs $ (i, j) \in \{1, \dots, n\}^2 $ (with $ i = j $ allowed) such that there exists an integer $ v \in \mathbb{Z}_{\ge 0} $ satisfying:
$$
\gcd(v, a_i) = X \quad \text{and} \quad \mathrm{lcm}(v, a_j) = Y
$$
API Response (JSON)
{
"problem": {
"name": "G. Appropriate Team",
"description": {
"content": "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 teammat",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1016G"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 teammat...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "由于下个赛季即将到来，你希望从两名或三名选手中组队。共有 $n$ 名候选人，第 $i$ 名候选人的排名为 $a_i$。但你对队友有奇怪的要求：如果你的排名为 $v$，并选择了第 $i$ 和第 $j$ 名候选人，则必须满足 $G C D (v, a_i) = X$ 且 $L C M (v, a_j) = Y$。\n\n你非常有经验，可以将你的排名改为任意非负整数，但 $X$ 和 $Y$ 与你的生日绑定，...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $, $ X, Y \\in \\mathbb{Z}^+ $ with $ 1 \\le X \\le Y $. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers, where $ a_i \\in \\mathbb{Z}^+ $ ...",
"is_translate": false,
"language": "Formal"
}
]
}