[蓝桥杯 2024 省 A] 因数计数

Luogu

IDLGP10390

Time1000ms

Memory512MB

DifficultyP5

高精度2024容斥原理蓝桥杯省赛

小蓝随手写出了含有 $n$ 个正整数的数组 $\{a_1, a_2,\cdots, a_n\}$，他发现可以轻松地算出有多少个有序二元组 $(i, j)$ 满足 $a_j$ 是 $a_i$ 的一个因数。因此他定义一个整数对 $(x_1, y_1)$ 是一个整数对 $(x_2, y_2)$ 的“因数”当且仅当 $x_1$ 和 $y_1$ 分别是 $x_2$ 和 $y_2$ 的因数。他想知道有多少个有序四元组 $(i, j, k, l)$ 满足 $(a_i , a_j)$ 是 $(a_k, a_l)$ 的因数，其中 $i, j, k, l$ 互不相等。 ## Input 输入的第一行包含一个正整数 $n$。第二行包含 $n$ 个正整数 $a_1, a_2,\cdots, a_n $，相邻整数之间使用一个空格分隔。 ## Output 输出一行包含一个整数表示答案。 [samples] ## Note 四元组 $(1, 4, 2, 3) $：$(3, 2)$ 为 $(6, 2)$ 的因子；四元组 $(1, 3, 2, 4) $：$(3, 2)$ 为 $(6, 2)$ 的因子；四元组 $(4, 1, 3, 2) $：$(2, 3)$ 为 $(2, 6)$ 的因子；四元组 $(3, 1, 4, 2) $：$(2, 3)$ 为 $(2, 6)$ 的因子。对于 $20\%$ 的评测用例，$n ≤ 50 $；对于 $40\%$ 的评测用例，$n ≤ 10^4$；对于所有评测用例，$1 ≤ n ≤ 10^5 ，1 ≤ a_i ≤ 10^5$。

Samples

Input #1

5
3 6 2 2 7

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[蓝桥杯 2024 省 A] 因数计数",
    "description": {
      "content": "小蓝随手写出了含有 $n$ 个正整数的数组 $\\{a_1, a_2,\\cdots, a_n\\}$，他发现可以轻松地算出有多少个有序二元组 $(i, j)$ 满足 $a_j$ 是 $a_i$ 的一个因数。因此他定义一个整数对 $(x_1, y_1)$ 是一个整数对 $(x_2, y_2)$ 的“因数”当且仅当 $x_1$ 和 $y_1$ 分别是 $x_2$ 和 $y_2$ 的因数。他想知道有多少个有",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10390"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小蓝随手写出了含有 $n$ 个正整数的数组 $\\{a_1, a_2,\\cdots, a_n\\}$，他发现可以轻松地算出有多少个有序二元组 $(i, j)$ 满足 $a_j$ 是 $a_i$ 的一个因数。因此他定义一个整数对 $(x_1, y_1)$ 是一个整数对 $(x_2, y_2)$ 的“因数”当且仅当 $x_1$ 和 $y_1$ 分别是 $x_2$ 和 $y_2$ 的因数。他想知道有多少个有...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments