{"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\nThe 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.\n\n## Output\n\nPrint one integer — the sum of _d_(_a__i_, _a__j_) over all pairs (_i_, _j_) such that 1 ≤ _i_ ≤ _j_ ≤ _n_.\n\n[samples]\n\n## Note\n\nIn 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.","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]$ 的元素个数。\\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$。 \"}]}","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 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$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF903D","tags":["data structures","math"],"sample_group":[["5\n1 2 3 1 3","4"],["4\n6 6 5 5","0"],["4\n6 6 4 4","\\-8"]],"created_at":"2026-03-03 11:00:39"}}