English · Original
Chinese · Translation
Formal · Original
Let's denote a function
You are given an array _a_ consisting of _n_ integers. You have to calculate the sum of _d_(_a__i_, _a__j_) over all pairs (_i_, _j_) such that 1 ≤ _i_ ≤ _j_ ≤ _n_.
## Input
The first line contains one integer _n_ (1 ≤ _n_ ≤ 200000) — the number of elements in _a_.
The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109) — elements of the array.
## Output
Print one integer — the sum of _d_(_a__i_, _a__j_) over all pairs (_i_, _j_) such that 1 ≤ _i_ ≤ _j_ ≤ _n_.
[samples]
## Note
In the first example:
1. _d_(_a_1, _a_2) = 0;
2. _d_(_a_1, _a_3) = 2;
3. _d_(_a_1, _a_4) = 0;
4. _d_(_a_1, _a_5) = 2;
5. _d_(_a_2, _a_3) = 0;
6. _d_(_a_2, _a_4) = 0;
7. _d_(_a_2, _a_5) = 0;
8. _d_(_a_3, _a_4) = - 2;
9. _d_(_a_3, _a_5) = 0;
10. _d_(_a_4, _a_5) = 2.
[{"iden":"statement","content":"设一个函数\n\n\n\n给定一个包含 $n$ 个整数的数组 $[a]$。你需要计算所有满足 $1 \\leq i \\leq j \\leq n$ 的数对 $(i, j)$ 的 $d(a_i, a_j)$ 之和。\n\n第一行包含一个整数 $n$ ($1 \\leq n \\leq 200000$) —— 数组 $[a]$ 的元素个数。\n\n第二行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$ ($1 \\leq a_i \\leq 10^9$) —— 数组的元素。\n\n请输出一个整数 —— 所有满足 $1 \\leq i \\leq j \\leq n$ 的数对 $(i, j)$ 的 $d(a_i, a_j)$ 之和。\n\n在第一个例子中：\n\n"},{"iden":"input","content":"第一行包含一个整数 $n$ ($1 \\leq n \\leq 200000$) —— 数组 $[a]$ 的元素个数。第二行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$ ($1 \\leq a_i \\leq 10^9$) —— 数组的元素。 "},{"iden":"output","content":"请输出一个整数 —— 所有满足 $1 \\leq i \\leq j \\leq n$ 的数对 $(i, j)$ 的 $d(a_i, a_j)$ 之和。"},{"iden":"examples","content":"输入\n5\n1 2 3 1 3\n输出\n4\n\n输入\n4\n6 6 5 5\n输出\n0\n\n输入\n4\n6 6 4 4\n输出\n-8"},{"iden":"note","content":"在第一个例子中：$d(a_1, a_2) = 0$；$d(a_1, a_3) = 2$；$d(a_1, a_4) = 0$；$d(a_1, a_5) = 2$；$d(a_2, a_3) = 0$；$d(a_2, a_4) = 0$；$d(a_2, a_5) = 0$；$d(a_3, a_4) = -2$；$d(a_3, a_5) = 0$；$d(a_4, a_5) = 2$。 "}]}
**Definitions**
Let $ n \in \mathbb{Z} $ be the length of the array.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers, where $ a_i \in \mathbb{Z}^+ $.
Let $ d(x, y) $ denote the number of distinct prime factors of $ \gcd(x, y) $.
**Constraints**
1. $ 1 \leq n \leq 200000 $
2. $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Compute:
$$
\sum_{1 \leq i \leq j \leq n} d(a_i, a_j)
$$
API Response (JSON)
{
"problem": {
"name": "D. Almost Difference",
"description": {
"content": "Let's denote a function You are given an array _a_ consisting of _n_ integers. You have to calculate the sum of _d_(_a__i_, _a__j_) over all pairs (_i_, _j_) such that 1 ≤ _i_ ≤ _j_ ≤ _n_.",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF903D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Let's denote a function\n\nYou are given an array _a_ consisting of _n_ integers. You have to calculate the sum of _d_(_a__i_, _a__j_) over all pairs (_i_, _j_) such that 1 ≤ _i_ ≤ _j_ ≤ _n_.\n\n## Input\n...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"设一个函数\\n\\n\\n\\n给定一个包含 $n$ 个整数的数组 $[a]$。你需要计算所有满足 $1 \\\\leq i \\\\leq j \\\\leq n$ 的数对 $(i, j)$ 的 $d(a_i, a_j)$ 之和。\\n\\n第一行包含一个整数 $n$ ($1 \\\\leq n \\\\leq 200000$) —— 数组 $[a]$ 的元素个...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ be the length of the array. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers, where $ a_i \\in \\mathbb{Z}^+ $. \nLet $ d(x, y) $ denote the numb...",
"is_translate": false,
"language": "Formal"
}
]
}