{"raw_statement":[{"iden":"statement","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_."},{"iden":"input","content":"The first line contains one integer _n_ (1 ≤ _n_ ≤ 200000) — the number of elements in _a_.\n\nThe second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109) — elements of the array."},{"iden":"output","content":"Print one integer — the sum of _d_(_a__i_, _a__j_) over all pairs (_i_, _j_) such that 1 ≤ _i_ ≤ _j_ ≤ _n_."},{"iden":"examples","content":"Input\n\n5\n1 2 3 1 3\n\nOutput\n\n4\n\nInput\n\n4\n6 6 5 5\n\nOutput\n\n0\n\nInput\n\n4\n6 6 4 4\n\nOutput\n\n\\-8"},{"iden":"note","content":"In the first example:\n\n1.  _d_(_a_1, _a_2) = 0;\n2.  _d_(_a_1, _a_3) = 2;\n3.  _d_(_a_1, _a_4) = 0;\n4.  _d_(_a_1, _a_5) = 2;\n5.  _d_(_a_2, _a_3) = 0;\n6.  _d_(_a_2, _a_4) = 0;\n7.  _d_(_a_2, _a_5) = 0;\n8.  _d_(_a_3, _a_4) =  - 2;\n9.  _d_(_a_3, _a_5) = 0;\n10.  _d_(_a_4, _a_5) = 2."}],"translated_statement":"[{\"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$。 \"}]}","sample_group":[],"show_order":[],"formal_statement":"**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 number of distinct prime factors of $ \\gcd(x, y) $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 200000 $  \n2. $ 1 \\leq a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nCompute:  \n$$\n\\sum_{1 \\leq i \\leq j \\leq n} d(a_i, a_j)\n$$","simple_statement":null,"has_page_source":false}